wamp 做网站发布,网页网站建设的ppt模板下载,阳江网,wordpress仿百度百家题目
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意#xff1a;解集不能包含重复的组合。
原题链接#xff1a;https://leetc…题目
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
原题链接https://leetcode.cn/problems/combination-sum-ii/description/
思路
dfs回溯。先对 candidates 进行排序。每次选定一个数字然后 target 减去该数字接着继续dfs。直到找到下一个数字刚好等于剩余target此时刚好找到一种组合如果下一个数字大于剩余target则直接返回。 排序主要是为了方便剪枝。作用体现在两方面
当 下一个数字大于剩余target时再下一个数字也一定大于剩余target。假如当前数字之前被选过了即不是第一次选该数字则也可以提前剪枝避免重复组合。
复杂度分析 时间复杂度 O(2^n)。每个数字都有选或不选的可能。空间复杂度 O(n)。空间复杂度取决于递归的栈深度。
代码
class Solution {
public:vectorvectorint result;
public:vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());vectorint temp;backtrace(candidates, temp, 0, target);return result;}void backtrace(vectorint candidates, vectorint 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();}}
};
