90. Subsets II

subsets([1,2,3,4]) = []
                     // push(1)
                     [1, subsets([2,3,4])] // if push N times in subsets([2,3,4]), the pop times is also N, so vec is also [1] after backtrack.
                     // pop(), push(2)
                     [2, subsets([3,4])]
                     // pop(), push(3)
                     [3, subsets([4])]
                     // pop(), push(4)
                     [4, subsets([])]
                     // pop()

代码参考

 1 class Solution {
 2 public:
 3     void subsets(vector<vector<int>>& res, vector<int>& nums, vector<int>& newv, int begin) {
 4         int j;
 5         res.push_back(newv);
 6         for(j = begin; j< nums.size(); j++){
 7             if(j>begin && nums[j]==nums[j-1]) continue;
 8             newv.push_back(nums[j]);
 9             subsets(res, nums, newv, j+1);
10             newv.pop_back();
11         }
12     }
13     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
14         vector<vector<int>> res = {};
15         vector<int> newv = {};
16         sort(nums.begin(), nums.end());
17         subsets(res, nums, newv, 0);
18         return res;
19     }
20 };