题目:Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.Each number in C may only be used once in the combination.
思路:深搜+动态规划
本题的区别就在于每个数字智能用一次,我开始的想法是我去除重复数字,后来例子才让我明白这样不对,因为每个数字都可以的。
还有就是,重复的力量非常可怕。去除重复的列子还记得吗?
本题直接的一个变化就是start+1,但是在前面需要判断的就是我需要判断前面是否存在这个temp
刚刚那个题目是数字可以多次利用,但不需判断是否存在,本身题目就没这个要求。已经试过。
而第二题,每个数字只用过一次,很容易造成使用很多次的结果,导致存在相同组合。
这个题目不需深究,本身leetcode有缺陷,如今,也算是见识到了。第一题,输入代码就是存在重复组合,而结果算是对的。
代码:
class Solution { public: //https://leetcode.com/problems/combination-sum-ii/ vector<int>temp; vector<vector<int> >result; vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); sumHelper(candidates,target,0,candidates.size()); return result; } void sumHelper(vector<int>& candidates,int target,int index,int length){ //index代表数组索引值,length代表数组长度 if(target==0){ //这里很巧的是,别人用sum求和,他不用,他是相减,只要等于0了,就会存入数组中。 if(find(result.begin(),result.end(),temp)==result.end()){ result.push_back(temp); } return;//不需要返回 } if(index>=length||target<0){//因为是求减法,如果不相等,立即返回|| //还有一种是索引值大于数组长度 return; } /* if (target < candidates[start]) { return; } It seems it is also ok */ for(int i=index;i<=length-1;i++){ temp.push_back(candidates[i]); sumHelper(candidates,target-candidates[i],i+1,length); temp.pop_back(); } } };