//另一种想法

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> out;
        sort(nums.begin(), nums.end());
        subsetsDFS(nums, 0, out, res);
        return res;
    }
    void subsetsDFS(vector<int>& nums, int start, vector<int>& out, vector<vector<int>>& res){
        res.push_back(out);
        for(int i=start;i<nums.size();i++){
            out.push_back(nums[i]);
            subsetsDFS(nums, i+1, out, res);
            out.pop_back();
        }
    }
};

class Solution
{
private:
	void RecGenerateSubsets(vector<vector<int>> &res, vector<int> &curSet, vector<int> &nums, int startIdx)
	{
		if (startIdx >= (int)nums.size()) return;

		int lastNum = nums[startIdx];
		curSet.push_back(lastNum);
		res.push_back(curSet);
		RecGenerateSubsets(res, curSet, nums, startIdx + 1);
		curSet.pop_back();
		for (size_t i = startIdx + 1; i < nums.size(); ++i)
		{
			if (lastNum == nums[i]) continue;
			else
			{
				lastNum = nums[i];
				curSet.push_back(lastNum);
				res.push_back(curSet);
				RecGenerateSubsets(res, curSet, nums, i + 1);
				curSet.pop_back();
			}
		}
	}
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums)
	{
		vector<vector<int>> res;

		if (nums.size() == 0) return res;

		sort(nums.begin(), nums.end());

		vector<int> curSet{};
		res.push_back(curSet);
		RecGenerateSubsets(res, curSet, nums, 0);

		return res;
    }
};

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        if(candidates.empty()){return res;}
        dfs(0,0,candidates,target);
        return res;
    }
    
    void dfs(int index,int sum,vector<int>& candidates,int target){
        if(sum==target){
            res.push_back(item);
            return;
        }
        else{
            for(int i=index;i<candidates.size();i++){
                if(i>index&&candidates[i]==candidates[i-1]){continue;}
                if(sum+candidates[i]<=target){
                    item.push_back(candidates[i]);
                    dfs(i+1,sum+candidates[i],candidates,target);
                    item.pop_back();
                }
                
            }
        }
    }
private:
    vector<vector<int>> res;
    vector<int> item;
};