Subset I, II and Perm I, II Difference Explained
There are many good posts explaining the backtrack idea of these two topics. \n\nThe subset and permutation problems all have similar code. However, I did not f
There are many good posts explaining the backtrack idea of these two topics. \n\nThe subset and permutation problems all have similar code. However, I did not find one that explains the difference between them. And despite the fact that they have similar code, actually they are very different.\n\n\n* subset I, II\nMy codes are similar to many others: push one element into the vector and then recursively call the function. After that pop that element out.\n**Explanation:** The subset problem is all about **choice**, whether you want certain element inside the vector or not. For example, [1, 2, 3], starting with pos = 0. At pos = 0, you push 1 into temp, then recursively call the function. Then this reclusive call is a "crossroad". Inside the call (with all other calls inside), you have the "1" chosen and every vector you produce will begin with 1. When the call returns (ie. you pop 1 out), you are on the other road of the crossroad, which does not contain 1. These are just the first "choice" you are faced. And after that you face with other similar choices. \n```\nclass Solution {\n    void helper(vector<vector<int>>& res, vector<int>& temp, vector<int>& nums, int pos){\n        res.push_back(temp);\n\n        for(int i=pos; i<nums.size(); ++i){\n            temp.push_back(nums[i]);\n            helper(res, temp, nums, i + 1);\n            temp.pop_back();\n        }\n\n    }\npublic:\n    vector<vector<int>> subsets(vector<int>& nums) {\n        vector<vector<int>> res;\n        vector<int> temp;\n        helper(res, temp, nums, 0);\n        return res;\n    }\n};\n```\n\n**subset II :** Eliminate the dup with sort and then the condition: do not put this element inside, if it has same element before && the former dup has not been put into it. Because otherwise, you better off put the former dup into the vector instead of this (latter dup) one. \n```\nclass Solution {\n    void helper(vector<vector<int>>& res, vector<int>& temp, vector<int>& nums, int pos){\n        res.push_back(temp);\n        \n        for(int i=pos; i<nums.size(); ++i){\n            if(i != pos && nums[i] == nums[i - 1]) continue;\n            temp.push_back(nums[i]);\n            helper(res, temp, nums, i + 1);\n            temp.pop_back();\n            \n        }\n    }\n    \npublic:\n    vector<vector<int>> subsetsWithDup(vector<int>& nums) {\n        vector<vector<int>> res;\n        vector<int> temp;\n        sort(nums.begin(), nums.end());\n        helper(res, temp, nums, 0);\n        return res;\n    }\n};\n```\n\n* Permutation I, II\nPermutation I is a very typical problem. \n\n**Note:** the pos here is different with the pos in subset. The pos in subset is more like choice in front of crossroad while the pos in permutation is the "digit" you are considering. In other words, you you consider the elements one by one: which one should be the first? which one should be the second? ...and so on. The **pos** is just the "first", "second"...\n\nWhen you consider the n**th** element, you swap the n**th** with element from n**th** to the last one, so that every element after that will have a chance to stay in the n**th** position. You recursively call, after each case.\n\n```\nclass Solution {\n    void helper(vector<vector<int>>& res, vector<int>& nums, int pos){\n        if(nums.size() == pos){\n            res.push_back(nums);\n            return ;\n        }\n        for(int i=pos; i < nums.size(); ++i){\n            swap(nums[i], nums[pos]);\n            helper(res, nums, pos + 1);\n            swap(nums[i], nums[pos]);\n        }\n    }\n    \npublic:\n    vector<vector<int>> permute(vector<int>& nums) {\n        vector<vector<int>> res;\n        helper(res, nums, 0);\n        return res;\n    }\n};\n```\n\npermutation II\nI prefer to use the unordered_map to solve the dup problem. How does it solve the problem? because it treats all the dup as one element with several copies. \n\nFor example, [1, 1, 2], when you iterate, in the same "level", the 1 will only be put once. We only put the other 1 into the vector in the recursive call in next levels.\n\n```\nclass Solution {\n    void helper(unordered_map<int, int>& bar, vector<int>& temp, vector<vector<int>>& res, int n){\n        if(temp.size() == n){\n            res.push_back(temp);\n            return ;\n        }\n        for(auto &i : bar){\n            if(i.second <= 0) continue;\n            i.second --;\n            temp.push_back(i.first);\n            helper(bar, temp, res, n);\n            temp.pop_back();\n            i.second ++;\n        }\n    }\n    \npublic:\n    vector<vector<int>> permuteUnique(vector<int>& nums) {\n        vector<vector<int>> res;\n        unordered_map<int, int> bar;\n        for(int i : nums){\n            bar[i] ++;\n        }\n        vector<int> temp;\n        helper(bar, temp, res, nums.size());\n        return res;\n    }\n};\n```
[]