# 90 - Subsets II

解法一 - Backtracking

這題避免重複的方法跟 # 40 - Combination Sum II 以及 # 47 - Permutation II 有異曲同工之妙，可以一起複習。

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;

        sort(nums.begin(), nums.end());
        helper(nums, res, tmp, 0);

        return res;
    }

private:
    void helper(vector<int>& nums, vector<vector<int>>& res, vector<int>& tmp, int start) {
        res.push_back(tmp);

        for(int i=start; i<nums.size(); i++) {
            if(i>start && nums[i] == nums[i-1]) continue;
            tmp.push_back(nums[i]);
            helper(nums, res, tmp, i+1);
            tmp.pop_back();
        }
    }
};

這個實作的效率還 OK： Runtime: 8 ms, faster than 84.71% of C++ online submissions for Subsets II. Memory Usage: 9.3 MB, less than 86.36% of C++ online submissions for Subsets II.