这篇文章可以说是全网最清楚如何淡化组合问题的文章了！组合sumII链接到链接：https://leetcode-cn.com/problems/combination-sum-ii/给定一个候选数组和一个目标数target，找出候选中所有可以使数字之和为target的组合.candidates中的每个数字在每个组合中只能使用一次。解释：所有数字（包括目标数字）都是正整数。解决方案集不能包含重复的组合。例1：输入：candidates=[10,1,2,7,6,1,5],target=8，解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]例2：输入：candidates=[2,5,2,1,2],target=5,解集为：[[1,2,2],[5]]本题与39.组合和的区别如下：本题考生中每个数在每个组合中只能使用一次。本题candidates数组元素重复，39.combinations之和为无重复元素的candidates数组。最后这道题和39一样，对组合之和的要求是一样的，解集不能有重复的组合。本题难点在于区别2：集合（数组候选项）有重复的元素，但不能有重复的组合。可能有的同学会想：我会把所有的组合都找出来，然后用set或者map去掉重复的。这样很容易超时！因此，在搜索过程中应删除重复的组合。很多同学想不通去重的问题。事实上，很多问题的解决方案都没有解释清楚。反正代码可以通过。为什么这个重复数据删除很难理解？所谓去重，其实就是用过的元素不能被重复选择。说起来好像很简单啊！我们都知道组合问题可以抽象成一个树结构，所以“used”在这个树结构中有两个维度，一个维度是在同一个分支上使用，另一个维度是同一个树层已经被使用。未能在这两个层面上理解“用过”，是大家对去重理解不全面的根本原因。那么问题来了，我们是要在同一个树层上还是在同一个分支上使用呢？回头看题，元素可以在同一个组合中重复。怎么重复都无所谓，但两个组合不能完全相同。所以我们要重复的是同一个树层上的“used”，同一个分支上的元素都是一个组合中的元素，就不用重复了。为了理解去重，举个例子，candidates=[1,1,2],target=3,(为了方便，候选已经排序)强调一下，如果对tree层进行去重，数组需要排序！选择过程树结构如图：图中可以看到CombinedsumII，每个节点都是相对于39的。我在combinedsum中添加了一个used数组，下面会高亮显示这个used数组。回溯三部曲的递归函数参数同39.组合和的套路。这道题需要用到一个bool数组，用来记录同一个分支上的元素是否被使用过。这个集合中去重的任务是由used完成的。代码如下：vector>result;//存储组合集合vectorpath;//限定组合voidbacktracking(vector&candidates,inttarget,intsum,intstartIndex,vector&used){递归终止条件同39.合并求和，终止条件为sum>target且sum==target。代码如下：if(sum>target){//这个条件其实可以省略return;}if(sum==target){result.push_back(path);return;}sum>target这个条件其实可以省略，因为和在递归遍历单层时，会有剪枝操作，下面会介绍。单层查找的逻辑和39.组合求和最大的区别就是需要重复。前面我们提到：需要强调的是“在同一个树层上使用”，如何判断同一个树层上的元素（同一个元素）是否被使用过。如果candidates[i]==candidates[i-1]andused[i-1]==false，表示：上一个分支使用了candidates[i-1]，也就是说同一层树已经使用了candidates[i-1]。这时continue操作应该在for循环中进行。这块比较抽象，如图：CombinationsumII1我在图中用橙色标注了used的变化，可以看出同样情况下candidates[i]==candidates[i-1]:used[i-1]==true，表示同一树分支的candidates[i-1]有使用used[i-1]==false，表示同一树层的candidates[i-1]有使用此重复数据删除逻辑。搜索问题的解决方案基本不清楚。如果你以前想过这个问题或者读过这个问题，看到这里你会感觉通透很多！那么单级搜索的逻辑代码如下：for(inti=startIndex;i0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}sum+=candidates[i];path.push_back(candidates[i]);used[i]=true;backtracking(candidates,target,sum,i+1,used);//和39.合并和1的区别：这里是i+1，每个数只能是每个组合使用一次used[i]=false;sum-=candidates[i];path.pop_back();}注意sum+candidates[i]<=target是一个剪枝操作，在39中已经解释过了。合计！回溯三部曲分析完毕，整体C++代码如下：artIndex,vector&used){if(sum==target){result.push_back(path);return;}for(inti=startIndex;i0&&candidates[i]==candidates[i-1]&&used[i-1]==false){continue;}sum+=candidates[i];path.push_back(candidates[i]);used[i]=true;backtracking(candidates,target,sum,i+1,used);//与39.合并和1的区别，这里是i+1，每个数字只能在每个组合中使用一次used[i]=false;sum-=candidates[i];path.pop_back();}}public:vector>combinationSum2(vector&candidates,inttarget){vectorused(candidates.size(),false);path.clear();result.clear();//首先对candidates进行排序，让相同的元素在后面相互排序（candidates.begin（），candidates.end（））;回溯（candidates,target,0,0,used);returnresult;}};也可以直接使用startIndex去重，所以used数组没有被使用。classSolution{private:vector>result;vectorpath;voidbacktracking(vector&candidates,inttarget,intsum,intstartIndex){if(sum==target){result.push_back(path);返回;}for(inti=startIndex;istartIndex&&candidates[i]==candidates[i-1]){continue;}sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i+1);//与39.合并和之差1，这里是i+1，每个数字在每个组合中只能使用一次sum-=candidates[i];path.pop_back();}}public:vector>combinationSum2(vector&candidates,inttarget){path.clear();result.clear();//首先对候选项进行排序，使相同的元素相邻。sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,0);returnresult;}};Summary这道题也是求组合之和，但是因为数组candidates有重复元素，并且要求不能有重复的组合，所以相比39.组合的总难度增加了很多。关键是去重的逻辑。代码非常简单。在网上查了很多，几乎没有一个能把这段代码的意思解释清楚。他们基本上给出了代码并说这是重复数据删除。怎么做？重法亦含糊。所以Carl有必要把去重给大家解释清楚。连“树层去重”和“分支去重”都是我造的词。希望对大家的理解有所帮助！其他语言版本JavaclassSolution{List>lists=newArrayList<>();Dequedeque=newLinkedList<>();intsum=0;publicList>combinationSum2(int[]candidates,inttarget){//为了把重复的数字放在一起，先排序Arrays.sort(candidates);//加入标志数组，辅助判断是否遍历了同级节点boolean[]flag=newboolean[candidates.length];backTracking(candidates,target,0,flag);returnlists;}publicvoidbackTracking(int[]arr,inttarget,intindex,boolean[]flag){if(sum==target){lists.add(newArrayList(deque));return;}for(inti=index;i0&&arr[i]==arr[i-1]&&!flag[i-1]){continue;}flag[i]=true;sum+=arr[i];deque.push(arr[i]);//每个节点只能选择一次，所以从下一位开始backTracking(arr,target,i+1,flag);inttemp=deque.pop();flag[i]=false;总和-=温度;}}}PythonclassSolution:defcombinationSum2(self,candidates:List[int],target:int)->List[List[int]]:res=[]path=[]defbacktrack(candidates,target,sum,startIndex):ifsum==target:res.append(路径[:])foriinrange(startIndex,len(candidates)):#跳过同一树层中使用的元素ifsum+candidates[i]>target:returnifi>startIndexandcandidates[i]==candidates[i-1]:continue#直接用startIndex去重，跳过同树层用到的元素sum+=candidates[i]path.append(candidates[i])backtrack(candidates,target,sum,i+1)#i+1:每个数在每个组合中只能使用一次sum-=candidates[i]#backtrackingpath.pop()#backtrackingcandidates=sorted(candidates)#首先对候选进行排序，使它们具有相同的元素并排在一起backtrack(candidates,target,0,0)returnresGo：主要是如何去重funccombinationSum2(candidates[]int,targetint)[][]int{vartrcak[]intvarres[][]intvarhistorymap[int]boolhistory=make(map[int]bool)sort.Ints(candidates)backtracking(0,0,target,candidates,trcak,&res,history)returnres}funcbacktracking(startIndex,sum,targetint,candidates,trcak[]int,res*[][]int,historymap[int]bool){//终止条件ifsum==target{tmp:=make([]int,len(trcak))copy(tmp,trcak)//copy*res=append(*res,tmp)//放入结果集return}ifsum>target{return}//backtracking//used[i-1]==true,表示同一个树分支candidates[i-1]已经被使用过//used[i-1]==false，表示同一树层的candidates[i-1]使用过fori:=startIndex;i0&&candidates[i]==candidates[i-1]&&history[i-1]==false{continue}//更新路径集合sumtrcak=append(trcak,candidates[i])sum+=candidates[i]history[i]=true//递归回溯(i+1,sum,target,candidates,trcak,res,history)//回溯trcak=trcak[:len(trcak)-1]sum-=candidates[i]history[i]=false}}
