391,回溯算法求组合问题

391,回溯算法求组合问题

Faith can move mountains.

信念能战胜一切。

 

问题一

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

 

说明:

所有数字(包括 target)都是正整数。

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

candidates 中的数字可以无限制重复被选取。

 

示例 1:

输入: candidates = [2,3,6,7]

target = 7

 

所求解集为:

[

  [7],

  [2,2,3]

]

示例 2:

输入: candidates = [2,3,5]

target = 8

 

所求解集为:

[

  [2,2,2,2],

  [2,3,3],

  [3,5]

]

 

问题分析

文中说的很明白,从candidates中找到一些数字让他们的和等于target,总共有多少种方式,并且candidates中的数字可以重复使用。我们可以先选择一个数字,用target减去他,然后再重复选择……,当target等于0的时候说明我们找到了一种组合。当target小于0的时候,说明没有找到合适的,我们回到上一步再重新选择数字……。看到这题我们首先想到的是N叉树,我们就以示例2为例画个图来看下

391,回溯算法求组合问题

这和二叉树的前序遍历非常相似,他先从根节点一直往左走,直到走到叶子节点为止,然后再回到父节点按同样的方式走右节点的路径,不了解前序遍历的可以看一下373,数据结构-6,树,代码如下

1public void preOrder(TreeNode tree) {
2    if (tree == null)
3        return;
4    System.out.println(tree.val);
5    preOrder(tree.left);
6    preOrder(tree.right);
7}

而N叉树的前序遍历和他类似

1public void preOrder(TreeNode tree) {
2    if (tree == null)
3        return;
4    System.out.println(tree.val);
5    preOrder("第一个子节点");
6    preOrder("第二个子节点");
7    ……
8    preOrder("第N个子节点");
9}

这样写也是可以的,但不方便,我们一般会使用一个for循环来写

1public void preOrder(TreeNode root) {
2    if (root == null)
3        return;
4    System.out.println(root.val);
5    //root.children获取root节点的所有子节点
6    for (int i = 0; i < root.children.size(); i++) {
7        preOrder(root.children.get(i));
8    }
9}

搞懂了上面的分析过程,代码就简单多了,我们来看下

 1public static List<List<Integer>> combinationSum(int[] candidates, int target) {
2    List<List<Integer>> result = new ArrayList<>();
3    backtrack(result, new ArrayList<>(), candidates, target);
4    return result;
5}
6
7private static void backtrack(List<List<Integer>> result, List<Integer> cur, int candidates[], int target) {
8    if (target == 0) {
9        result.add(new ArrayList<>(cur));
10        return;
11    }
12    //相当于遍历N叉树的子节点
13    for (int i = 0; i < candidates.length; i++) {
14        //如果当前节点大于target我们就不要选了
15        if (target < candidates[i])
16            continue;
17        //由于在java中List是引用传递,所以这里要重新创建一个
18        List<Integer> list = new ArrayList<>(cur);
19        list.add(candidates[i]);
20        backtrack(result, list, candidates, target - candidates[i]);
21    }
22}

我们来看下运行结果

  •  
[2, 2, 2, 2][2, 3, 3][3, 2, 3][3, 3, 2][3, 5][5, 3]

完全出乎我们的意料之外,这是因为出现了重复的数据,[2,3,3],[3,2,3],[3,3,2]其实应该只算一个。在上面的图中我们分析过,如果选择了后面的数字就不能再选择前面的了,因为这样会出现重复,所以我们可以添加一个变量start表示访问的数组中元素的位置,我们只能访问start和start后面的数字,我们再来看下代码

 1public static List<List<Integer>> combinationSum(int[] candidates, int target) {
2    List<List<Integer>> result = new ArrayList<>();
3    backtrack(result, new ArrayList<>(), candidates, target, 0);
4    return result;
5}
6
7private static void backtrack(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start) {
8    if (target == 0) {
9        result.add(new ArrayList<>(cur));
10        return;
11    }
12    //相当于遍历N叉树的子节点
13    for (int i = start; i < candidates.length; i++) {
14        //如果当前节点大于target我们就不要选了
15        if (target < candidates[i])
16            continue;
17        //由于在java中List是引用传递,所以这里要重新创建一个
18        List<Integer> list = new ArrayList<>(cur);
19        list.add(candidates[i]);
20        backtrack(result, list, candidates, target - candidates[i], i);
21    }
22}

注意这里第13行的for循环不是从0开始了,再来看下运行结果

  •  
[2, 2, 2, 2][2, 3, 3][3, 5]

和我们图中分析的完全一致,并且也没有了重复的。在上面的18行我们是新建了一个list,其实我们还可以不用新建,在回溯的时候把它移除即可,可以这样写

 1public static List<List<Integer>> combinationSum(int[] candidates, int target) {
2    List<List<Integer>> result = new ArrayList<>();
3    getResult(result, new ArrayList<>(), candidates, target, 0);
4    return result;
5}
6
7
8private static void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start) {
9    if (target == 0) {
10        result.add(new ArrayList<>(cur));
11        return;
12    }
13    for (int i = start; i < candidates.length; i++) {
14        if (target < candidates[i])
15            continue;
16        //选择当前节点,类似于从当前节点开始往下遍历
17        cur.add(candidates[i]);
18        getResult(result, cur, candidates, target - candidates[i], i);
19        //回到当前节点的时候我们把当前节点给移除,
20        // 然后通过循环走同一层的其他节点。
21        //举个例子,比如上面图中,最开始的时候
22        // 我们先选择2,然后沿着这个分支走下去,
23        //当回到当前分支的时候我们把2给移除,然后
24        // 选择同一层的下一个3,沿着这个节点
25        //分支走下去……
26        cur.remove(cur.size() - 1);
27    }
28}

搞懂了上面的题,我们再来看一个非常相似的题

 

问题二

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 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]

]

 

问题分析

这道题和第一道题不同的是,这道题数组中的数字只能被选择一次,而第一道题数组中的数字可以被选中无数次。解题思想还是一样的,我们要做的是怎么过滤掉重复的,首先可以对原数组进行排序,排序之后相同的肯定是挨着的,if(candidates[i] == candidates[i - 1])我们就过滤掉candidates[i],我们就仿照第一道题来写下这道题的答案

 1public List<List<Integer>> combinationSum2(int[] candidates, int target) {
2    List<List<Integer>> list = new LinkedList<>();
3    Arrays.sort(candidates);//先排序
4    backtrack(list, new ArrayList<>(), candidates, target, 0);
5    return list;
6}
7
8private void backtrack(List<List<Integer>> list, List<Integer> cur, int[] candidates, int target, int start) {
9    if (target == 0) {
10        list.add(new ArrayList<>(cur));
11        return;
12    }
13    for (int i = start; i < candidates.length; i++) {
14        if (target < candidates[i])
15            continue;
16        if (i > start && candidates[i] == candidates[i - 1])
17            continue; //去掉重复的
18        cur.add(candidates[i]);
19        backtrack(list, cur, candidates, target - candidates[i], i + 1);
20        cur.remove(cur.size() - 1);
21    }
22}

我们发现和第一道题很相似,只不过在第3行先做了排序,第16-17行做了去重,由于不能选择重复的,所以在第19行选择一个之后我们从当前元素的下一个进行选择

 

总结

类似这样的题我们可以把它想象为一棵N叉树,我们先选择一个,然后再递归选择(根据是否可以选择重复的有不同的选择,如果允许有重复的,我们递归的时候还可以再选择当前的,如果不允许有重复的,我们递归的时候就从当前的下一个开始选择),沿着这个分支走完之后我们会把当前节点删除,然后再从下一个分支走……

 

 

391,回溯算法求组合问题

373,数据结构-6,树

371,背包问题系列之-基础背包问题

372,二叉树的最近公共祖先

387,二叉树中的最大路径和

 

 

391,回溯算法求组合问题

长按上图,识别图中二维码之后即可关注。

 

如果喜欢这篇文章就点个"在看"吧

上一篇:递归回溯中的一些套路


下一篇:【回溯算法】四、回溯模板