90-Subsets II

tags: Medium

• Question:
  https://leetcode.com/problems/subsets-ii/

Key:

1. 看到subset先試試Backtracking
2. 相較Subset I這題多了重複的問題，所以先進行排序，能夠比較前後元素是否相同，如果相同的話，就先skip(不丟元素到subset中)，然後更新i，才能做下一次比較，且為了確保i-1>0，i必須大於遍尋的初始值(begin)
   ex. nums=[1,2,2,2,3,3]

Reference:
https://medium.com/@ChYuan/leetcode-90-subsets-ii-心得-medium-f6eaa6f6ee23

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