通过DFS实现回溯,关键在于两点:

  1. 去重(好好理解一下)
  2. 剪枝(不剪枝会超时)
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();
            }
        }
    }
};