0

I have tried to solve a problem of generating all subsets of an array which contains no duplicates from leetcode : https://leetcode.com/problems/subsets/ . e.g if input is [1,2,3], output should be [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]].

Since we need to generate all subsets, its a backtracking problem. I figured the states, decisions and base cases. Decision will be that we have to include the current element and move forward and next time exclude it and move forward. The code will look like :

vector<vector<int>> subsets(vector<int>& nums) { // nums is our input array
        vector<int> res;
        vector<vector<int>> final_res;
        
        if(nums.empty())
            return {};
        
        subsetsUtil(nums, 0, nums.size(), res, final_res);
        return final_res;
    }
    
    void subsetsUtil(vector<int> &nums, int i, int n, vector<int> res, vector<vector<int>> &final_res) {
        
      if (i == n) {
            final_res.push_back(res);
             return;
        }
        
        res.push_back(nums[i]);
        subsetsUtil(nums, i+1, n, res, final_res); // include
        res.pop_back();
        subsetsUtil(nums, i+1, n, res, final_res);   // exclude
       
    }
};

Now I have changed the implementation of susbsetsUtil and The same problem can be implemented using the for loop in the below code snippet. Is the same approach of include/exclude is used in the for loop ? If yes, I am not able to visualize that how is include/exclude approach is translated to the for loop below. Also are there some good resources to learn about the backtracking patterns and to master it. Thanks !

 void subsetsUtil(vector<int> &nums, int i, int n, vector<int> res, vector<vector<int>> &final_res) {
        
        final_res.push_back(res);
               
        for (int index = i; index < n; index++) {
            res.push_back(nums[index]);
            subsetsUtil(nums, index+1, n, res, final_res);
            res.pop_back();
        }
    }
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Nerd
  • 43
  • 7
  • Can anybody explain this? Thanks – Nerd Nov 30 '20 at 04:40
  • 1. have you tested your first code snippet? 2. is it working? 3. do you understand why / how? – Will Ness Nov 30 '20 at 10:44
  • 4. (1,2) for the second snippet. ---- see https://stackoverflow.com/questions/65066122/turning-a-recursion-into-an-iteration-in-java/65066207#65066207 for a very similar situation. if you can visualize the first, you'll see the second does the same thing (IIANM). – Will Ness Nov 30 '20 at 10:53
  • as for the resources, you could browse through [this answer](https://stackoverflow.com/a/61216006/849891) of mine, and follow the links in it (also, https://cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html). there are two c++ links at the bottom of that answer, too. I also once wrote [this](https://en.wikipedia.org/w/index.php?title=Recursion&oldid=932978971#Informal_definition) (search for "maze") but it got reverted. also, [this answer](https://stackoverflow.com/a/27804489/849891). see it any of this helps. – Will Ness Nov 30 '20 at 11:11

0 Answers0