力扣：组合之和2java

力扣：组合之和2java

流程：
定义一个二维数组结果集和一维数组path和使用过的元素数组use
对数组进行排序（方便对树层剪枝）
回溯三部曲：
参数和返回值：返回值为空，参数为数组candidates、目标值targer、开始下标startindex
结束条件：targer等于0，path输入结果集并返回上一层。targer<0，直接返回上一层
单层递归逻辑：

• for循环（int i=startindex；i小于数组的长度；i++）
• • 树层剪枝：判断当前节点是否与前一节点相同并且前一节点的use值等于false（表示前一节点是回溯后的）
• • 节点操作：对sum加上该节点的值，将该节点输入path，当前节点的use赋值为true。
• • 递归（数组candidates，当前目标值targer，i+1）
• • 回溯操作：sum减当前值，节点弹出path，当前节点的use赋值为false

代码：

class Solution {
    List<List<Integer>> result = new ArrayList<>();//结果集
    LinkedList<Integer> path = new LinkedList<>();//路径path
    boolean[] use;//使用数组，用判断当前节点是否被使用过
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {//主函数
        use = new boolean[candidates.length]; //对use数组定义并赋值
        Arrays.fill(use,false);
        Arrays.sort(candidates); //use数组排序方便去重
        sumcombination2(candidates,target,0);//调用递归函数
        return result;
    }
    public void sumcombination2(int[] candidates,int target,int startindex){
        if(target == 0){//结束条件，当前目标值等于0，则路径加入结果集并返回上一层
            result.add(new ArrayList(path));
            return;
        }
        if(target < 0){//小于0，则不符合，直接返回上一层
            return;
        }
        for(int i = startindex;i<candidates.length;i++){//遍历
            if(i>0&&candidates[i-1] == candidates[i]&& use[i-1] == false){//去重，与前一节相同，并且前一节点的use是false，保证当前节点是回溯后的
                continue;
            }
            path.add(candidates[i]);//当前节点加入路径
            target-=candidates[i];//目标值减当前值
            use[i] = true;//当前节点的use赋true
            sumcombination2(candidates,target,i+1);//递归下一层
            path.removeLast();//回溯，path的当前节点弹出
            target+=candidates[i];//目标值加回来
            use[i] = false;//ues也重新赋值为ture
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33