leetcode 40. 组合总和 II

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

原题链接：https://leetcode.cn/problems/combination-sum-ii/description/

思路

dfs回溯。先对 candidates 进行排序。每次选定一个数字，然后 target 减去该数字，接着继续dfs。直到找到下一个数字刚好等于剩余target，此时刚好找到一种组合；如果下一个数字大于剩余target，则直接返回。
排序主要是为了方便剪枝。作用体现在两方面：

1. 当 下一个数字大于剩余target时，再下一个数字也一定大于剩余target。
2. 假如当前数字之前被选过了，即不是第一次选该数字，则也可以提前剪枝，避免重复组合。

• 复杂度分析
  • 时间复杂度 O(2^n)。每个数字都有选或不选的可能。
  • 空间复杂度 O(n)。空间复杂度取决于递归的栈深度。

代码

class Solution {
public:vector<vector<int>> result;
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());vector<int> temp;backtrace(candidates, temp, 0, target);return result;}void backtrace(vector<int>& candidates, vector<int>& temp, int start, int target) {if (target == 0) {result.push_back(temp);return;}for (int i = start; i < candidates.size(); i++) {if (i > start && candidates[i] == candidates[i - 1]) {continue;}if (candidates[i] > target) {break;}temp.push_back(candidates[i]);backtrace(candidates, temp, i + 1, target - candidates[i]);temp.pop_back();}}
};