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

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > res;
        vector<int> tmp;
        //初始化
        if (num.empty()) return res;
        //特殊情况处理
        sort(num.begin(), num.end());
        //排序
        dfs(num, target, res, tmp, 0);
        //计算
        return res;
    }

    void dfs(vector<int> &num, int target, vector<vector<int> > &res, vector<int> &tmp, int start) {
        if (target == 0) {
            res.push_back(tmp);//结束条件，找到一条路径后保存
            return;
        }
        if (start >= num.size()) return;//越界返回
        
        for (int i = start; i < num.size(); ++i) {
            if (i > start && num[i] == num[i-1]) continue;  // 去重
            if (num[i] <= target) {                         // 剪枝
                tmp.push_back(num[i]);
                dfs(num, target - num[i], res, tmp, i + 1);  //递归
                tmp.pop_back();
            }
        }
    }
};