# Subsets — I

`Input: nums = [1,2,3]Output:[  ,  ,  ,  [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)                    /                    \              (,[2,3])                ([],[2,3])      (choose 2)/ \(don't choose 2)  (choose 2)/ \(don't choose 2)                   /   \                         /   \       ([1,2],)  (,)          (,)   ([],)(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 1class 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

`// BACKTRACKING 2class 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

`//ITERATIVEclass 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:[  ,  ,  [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;  }};`

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

--

--

## More from Manvi Tyagi

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