题解 | #加起来和为目标值的组合#

class Solution {
public:
    void dfs(vector<vector<int >>& res, vector<int>& ans, vector<int>& num, vector<bool>& used, int target, int selSum, int startIndex) {
        if(selSum == target) {
            res.push_back(ans);
            return;
        }
        for(int i = startIndex; i < num.size(); i++) { // i从startIndex开始遍历，保证数组从小到大按照顺序遍历
            if(!used[i] && selSum + num[i] <= target) {
                if(i > 0 && num[i]==num[i-1] && used[i-1]==false) // 剪枝掉相同数组
                   continue;
                used[i] = true;
                ans.push_back(num[i]);
                dfs(res, ans, num, used, target, selSum + num[i], i + 1);
                used[i] = false;
                ans.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        vector<vector<int>> res;
        vector<int> ans;
        vector<bool> used(num.size(), false);
        int selSum = 0;
        int startIndex = 0;
        dfs(res, ans, num, used, target, selSum, startIndex);
        return res;
    }
};