本文共 1238 字，大约阅读时间需要 4 分钟。

Leedcode40——组合总和II(回溯法)

一.思路

题目描述:

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

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

说明：

所有数字（包括目标数）都是正整数。

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

例子讲解

[1,2,6,1]

这个例子的结果为:

[

[2, 6],

[1, 1, 6]

]

我们采用回溯的思想:

首先我们按升序排好序[1，1，2，6] 按后我们倒着来回溯(即6放在最上面)，状态树如下: 注意两点就是: ①并不是每个节点对应的只就是他前面节点与他加起来，比如6，2，1这一路就是有可能2这个地方对应的值是6+2=8，也有可能是6没被考虑直接是2 ②每个点他的子节点都是他左边的数，比如6，他左边是2，1，1，因此他下面的节点就是2，1，1

二.代码实现

public class Solution {
       public List
   
    
     > combinationSum2(int[] candidates, int target) {
           Arrays.sort(candidates);        List
     
      
       > lists = new ArrayList<>();        List
       
         list = new ArrayList<>();        int []flag = new int[candidates.length];        combinationSum(candidates,target,lists,0,list,flag,candidates.length-1);        return lists;    }    void  combinationSum(int []candidates,int target,List
        
         
          > lists,int curr,List
          
            list,int []flag,int start){ int last=start+1; for(int i=start;i>=0;i--){ //防止出现重复，于是把同一层里面当前节点如果与上一个一样就跳过 if(last==start+1||candidates[i]!=candidates[last]){ if(curr+candidates[i]
           
             list_new= new ArrayList<>(); for (Integer integer : list) { list_new.add(integer); } lists.add(list_new); list.remove(list.size()-1); } } last=i; } }}
           
          
         
        
       
      
     
    
   

转载地址：http://ltlzi.baihongyu.com/