如何分析竞争对手网站,php做的网站如何发布,环保类网站建设,山东省住房和城乡建设挺网站题目
给定一个数组 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。
思考以及代码
如果我们直接套用39题的思路#xff0c;那么就会出现重复的组合。 重复组合的…题目
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。
思考以及代码
如果我们直接套用39题的思路那么就会出现重复的组合。 重复组合的产生是因为集合中有重复的元素。 去重就是使用过的元素不能重复选取。 我们result的重复组合的产生肯定是和重复元素有关的我们从解空间树的深度(递归调用)和宽度(for循环)来看 1、元素的重复的影响可能出现在在解空间树的宽度和深度上。 2、宽度上的重复决定了我们result解的组合的重复深度上的重复决定了result解的每个子结果res的元素重复。 3、结合题意如果是在宽度上重复我们需要去除如果是在深度上重复我们不需要去除。
在宽度上进行去重所以我们在for循环的过程中加入限制。
//如果遇到同一个集合的重复元素跳过这个元素即可
if(i startindex candidates[i] candidates[i-1]) continue;注意这里我们已经对原数组进行排序了所以重复的元素一定靠在一起
class Solution {
public:vectorvectorint result;vectorint res;int sum;void clear_solution_param(){result.clear();res.clear();sum0;}void backtracking(vectorint candidates,int startindex,int n){ if(sum n) return;if(sum n){result.push_back(res);return;}for(int istartindex;icandidates.size();i){//由于输入的数组是有序的所以直接进行剪枝。如果sum加上这个集合元素大于目标此层就不需要往后看了因为后面的元素加上sum肯定大于目标if(sumcandidates[i]n) break;//如果遇到同一个集合的重复元素跳过这个元素即可if(i startindex candidates[i] candidates[i-1]) continue;//处理结点res.push_back(candidates[i]);sumcandidates[i];//递归,探索下一层backtracking(candidates,i1,n); //递归sum-candidates[i];//回溯撤销处理结果res.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {clear_solution_param();//排序加速剪枝sort(candidates.begin(),candidates.end());backtracking(candidates,0,target);return result;}
};
