Backtracking (Subsets Problem)— Part 2

Subsets — I

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

THREE DIFFERENT SOLUTIONS

1. THOUGHT PROCESS FOR 1st BACKTRACKING SOLUTION

Take example of [1,2,3].([ans],[nums])
([],[1,2,3])
(choose 1) / \ (don't choose 1)
/ \
([1],[2,3]) ([],[2,3])
(choose 2)/ \(don't choose 2) (choose 2)/ \(don't choose 2)
/ \ / \
([1,2],[3]) ([1],[3]) ([2],[3]) ([],[3])
(choose 3)/ \(don't choose 3) ....................................
/ \
([1,2,3],[]) ([1,2],[]) ([1,3],[]) ([1,3],[]).......
(Base cases when nums is empty)
PS: Please try this on paper and pardon me if the tree doesn't look good :)
//BACKTRACKING 1
class Solution {
public:
vector<vector<int>> ans;
void subsets(vector<int>& nums, vector<int> &currset, int start){

//base case
if(start == nums.size()){
ans.push_back(currset);
return;
}


//for every elt in nums, we have 2 choices

//choice 1 : keep it in currans
currset.push_back(nums[start]);
subsets(nums,currset,start+1);

//choice 2 : Don't keep it in currans
currset.pop_back();
subsets(nums,currset,start+1);

}

vector<vector<int>> subsets(vector<int>& nums) {
vector<int> currans = {};

subsets(nums,currans,0);

return ans;
}
};

2. THOUGHT PROCESS FOR 2nd BACKTRACKING SOLUTION

Recursive Tree
// BACKTRACKING 2
class Solution {
public:
vector<vector<int>> ans;

void subsets(vector<int> nums, int start, vector<int> currset){
ans.push_back(currset)
//base case
if(start == nums.size()){
return;
}
for(int j = start; j < nums.size(); j++){
currset.push_back(nums[j]);
subsets(nums,j+1,currset);
currset.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
subsets(nums,0,{});
return ans;
}
};

3. THOUGHT PROCESS FOR ITERATIVE SOLUTION

Iterative Solution exists amidst the popularity of recursive backtracking solutions.
//ITERATIVE
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans= {{}};
for (int num : nums) {
int n = ans.size();
for (int i = 0; i < n; i++) {
ans.push_back(subs[i]);
ans.back().push_back(num);
}
}
return ans;
}
};

Subsets — II

Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

THOUGHT PROCESS

class Solution
{
public:
vector<vector<int>> ans;
void helper(vector<int> &nums, vector<int> &currans, int start)
{
ans.push_back(currans);
for (int i = start; i < nums.size(); i++)
{
if (i > start && nums[i] == nums[i - 1])
continue;
currans.push_back(nums[i]);
helper(nums,currans,i+1);
currans.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int> &nums)
{
sort(nums.begin(), nums.end());
vector<int> currans = {};
helper(nums, currans, 0);
return ans;
}
};

THANK YOU FOR READING. All your suggestions are welcomed. Encourage me to write more by appreciating if you like the article.

SEE YOU IN THE NEXT PART WITH QUESTIONS RELATED TO PERMUTATIONS :)

--

--

Software Developer working to become a better Software Developer everyday :)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Manvi Tyagi

Software Developer working to become a better Software Developer everyday :)