通过DFS实现回溯,关键在于两点:
- 去重(好好理解一下)
- 剪枝(不剪枝会超时)
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(); } } } };