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

DFS + 回溯

class Solution {
public:
    void dfs(vector<int> &num, int target, vector<vector<int> > &ans, vector<int> &tmp, int start) {
        if (target == 0) {
            ans.push_back(tmp);  // 满足等于目标值
            return;
        }
        if (start >= num.size()) return;  // 越界
        for (int i = start; i < num.size(); ++i) {  // 从start 开始遍历
            if (i > start && num[i] == num[i-1]) continue; // 去除重复数字
            if (num[i] <= target) {   //剪枝
                // 回溯
                tmp.push_back(num[i]);
                dfs(num, target-num[i], ans, tmp, i+1);
                tmp.pop_back();
            }
        }
    }

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > ans;
        if (num.empty()) return ans;
        vector<int> tmp;
        sort(num.begin(), num.end());  // 排序，为去重做准备
        dfs(num, target, ans, tmp, 0);  // 从0开始dfs
        return ans;
    }
};