组合总和2—回溯

发布: 分类: 评论次数： 阅读次数： 本文字数： 1.3k

今天的这道题依旧是回溯的经典模版，仅用来提醒以后的自己，回溯并不是十分的可怕～

顺带闲聊下，今天的上海，天气还是老样子，晴着晴着就开始下雨了，整的我又只能在图书馆里的FamilyMart里弄点吃的了（偷偷吐槽下，是真的不好吃～）

又是无聊的一天，今天的我是不是比昨天又厉害了点呢？好像也没干啥事，上午的我将自然辩证法的考点写了点，准备开背。。。中午呢，老样子，看番（嘻嘻嘻嘻），下午就开始刷了一道题（就是被这台mac整的，环境咋这么难配）。不知道大家今天又有什么开心难过烦恼的事呢？都可以说给我听的哟～

题目介绍

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

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

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

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

我的思路

这道题和我博客上的上一道题其实上是很相似的（这也是为啥我可以独自做出来的原因～），从方法上来看，都是经典的回溯，技巧上呢，肯定是包括了上次那道题的防重复设置啦，除此之外，由于这道题中的选择项不可以是无限量的，也就是说列表是会变化的

因此，可以设置一个标志数组，用来判断某个选择项是否已经被使用过（无论是使用，还是撤销，都必须记得还原标记）

因为每个选择项只能用一次的原因，上面说的那种防重复设置就会有所缺陷，比如说：

1
2
3
4
5
6
7
8
9
输入: candidates = [2,5,2,1,2], target = 5,

首先对选择列表排个序：1,2,2,2,5
(1)往已选列表中添加1，sum = 1，i = 0  [1]
(2)往已选列表中添加2，sum = 3，i = 1  [1,2]
(3)往已选列表中添加2，sum = 5，i = 2  [1,2,2]  符合条件，加入结果
(4)撤销，i = 1 [1,2]
(5)往已选列表中添加2，sum = 5，i = 3  [1,2,2]  重复

上面的例子中，第5步中添加的2下标是3，在此之前并未被使用过，因此如果按照之前的防重复设置，不会被排除，所以需要重新设计一下

可以看出，上面的例子中重复数字是在撤销后再次选择时发生的，当然，可能也会在回溯到顶点的时候出现这种情况，比如说： [1,1,2,5,6,7,10]，target = 8，开始以1往下走，会得到[1,2,5]，当1结束后，也就是已选列表空的时候，会以第二个1为顶点，继续往下走，这样又会得到一次[1,2,5]

因此，既然是两者都是在撤销之后，继续添加下一个数的时候出现这种情况，那么，只要跳过与当前撤销值相等的选项不就可以了嘛

注意：什么时候会撤销呢？只有当回溯返回后，才会撤销，也就是说要么当前已选列表符合条件，撤销末尾两个值（两个值的原因很简单，因为撤销末尾值后，如果还想符合条件，肯定是加入一个和撤销值一样的数，那样直接重复），要么就是目前的已选列表不管怎么选都不可能再符合条件，撤销末尾的值（一般是撤销两个，因为将选择列表排序后，如果一开始的末尾数不行，加上下一个数肯定不行）

代码

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
34
35
36
37
38
39
40
41
42
43
44
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Boolean[] tag = new Boolean[candidates.length];
    for(int i=0;i<tag.length;i++){
        tag[i] = true;
    }
    List<Integer> ans = new ArrayList<>();
    List<List<Integer>> ret = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(candidates,target,0,ans,ret,0,tag);
    return ret;
}

private void backtrack(int[] candidates, int target, int sum, List<Integer> ans, List<List<Integer>> ret, int begin, Boolean[] tag){
    if(sum == target){
        List<Integer> temp = new ArrayList<>(ans);
        ret.add(temp);
        return;
    }

    for(int i=begin;i<candidates.length;i++){
        if(tag[i] == true){
            ans.add(candidates[i]);
            sum += candidates[i];
            tag[i] = false;
        }else{
            continue;
        }
        if(sum > target){
            ans.remove(ans.size()-1);
            sum -= candidates[i];
            tag[i] = true;
            break;
        }
        backtrack(candidates,target,sum,ans,ret,i,tag);
        ans.remove(ans.size()-1);
        sum -= candidates[i];
        tag[i] = true;

        while (i < candidates.length-1 && candidates[i+1] == candidates[i]){
            i++;
        }
    }
    return;
}

代码中有一个地方没怎么写好，大家可以自己去改下，就是当目前的已选列表符合条件后，返回后撤销的时候，一定会撤销两个值（可以这么设计，在代码开头，再加个判断，如果sum>target，直接return，然后呢，将for循环中的sum>target改为sum>=target，并放在回溯的后面即可）

老实说，回溯可以这么来想，凡是回溯这行代码之前的，总是会被执行，回溯之后的代码，只有return后才会被执行（可能是符合条件，也可能是再也不可能符合条件）

结束

又到8:30了，时间真的好快，快的我都追不上了～

转眼间，我的研究生生活好像过了不少了啊，，可是未来还是如雾般难以捉摸，（开心好难～）