回溯算法复习

本文最后更新于：2022年7月3日 下午

回溯算法复习

题目来源：力扣

39. 组合总和

题目描述

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

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

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

1
2
3
4
5
6
7
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思想

因为题目中每个数字可以重复使用多次，那么我们就可以画出如下的图，利用回溯算法进行选择，开始写代码。

排序后进行剪枝更加的高效，首先上图中，因为每个数字都要被重复的使用，那么例如[1,3,9,5,2]中，我们如果不进行排序，那么只有在

解题代码

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length==0){
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        //排序后进行剪枝更加的高效
        Arrays.sort(candidates);
        dfs(candidates,0,target,new ArrayDeque<Integer>(),result);
        return result;
    }
    public void dfs(int[] candidates,int begin,int target,Deque<Integer> path,List<List<Integer>> result){
        if(target==0){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        //为什么从begin开始？，因为我们的数组是无重复的，那么数组如果已经进行到了第i个元素，
        //那么0到（i-1）中的每个结果都被包括在结集中，所以不用进行重复的考虑
        for(int i=begin;i<candidates.length;i++){
            if(target-candidates[i]<0){
                break;
            }
            path.addLast(candidates[i]);
            dfs(candidates,i,target-candidates[i],path,result);
            path.removeLast();
        }

    }
}

40. 组合总和 II

题目描述

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

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

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思想

此题与上题组合总和不同点在于，本题目中的数组中的元素只能使用一次，那么我们就要考虑如何去重重复：先对数组 升序 排序，重复的元素一定不是排好序以后相同的连续数组区域的第 1 个元素。也就是说，剪枝发生在：同一层数值相同的结点第 2、3 … 个结点，因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果。那么我们就可以使用语句

1
2
3
4
5
for(int i=begin;i<candidates.length;i++){
	if(candidates[i]==candidates[i-1]){
    	continue;
    //do somethng！
    }

进行剪枝

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题代码

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
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates.length==0){
            return new ArrayList<List<Integer>>();
        }
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        dfs(candidates,target,new ArrayDeque<Integer>(),result,0);
        return result;
    }
    public void dfs(int[] candidates, int target,Deque<Integer> path,List<List<Integer>> result,int begin){
        if(target==0){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=begin;i<candidates.length;i++){
            if(target-candidates[i]<0){
                break;
            }
            //解释一下这句话，i>begin保证了两个相同的数不会出现在同一层级
            //candidates[i]==candidates[i-1]保证了同一层不会出现重复元素的
            if(i>begin&&candidates[i]==candidates[i-1]){
                continue;
            }
            path.addLast(candidates[i]);
            dfs(candidates,target-candidates[i],path,result,i+1);
            path.removeLast();
        }
    }
}

216. 组合总和 III

题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

1
2
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思想

思想和上面一样，不再赘述了。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        dfs(k,n,result,1,new ArrayDeque<Integer>());
        return result;
    }
    public void dfs(int k, int n,List<List<Integer>> result,int begin,Deque<Integer> path){
        if(path.size()==k&&n==0){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        if(path.size()>k||n<0){
            return;
        }
        for(int i=begin;i<=9;i++){
            if(n-i<0){
                break;
            }
            path.add(i);
            dfs(k,n-i,result,i+1,path);
            path.removeLast();
        }
    }
}

46. 全排列

题目描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思想

回溯法，和上面一样，思路的话，组成和途中一样的树，不过判断条件不同，是将

解题代码

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(nums==null){
            return result;
        }
        dfs(nums,result,new ArrayDeque<Integer>(),new boolean[nums.length]);
        return result;
    }

    public void dfs(int[] nums,List<List<Integer>> result,Deque<Integer> path,boolean[] used){
        if(path.size()==nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            dfs(nums,result,path,used);
            used[i]=false;
            path.removeLast();
        }
    }
}

47. 全排列 II

题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思想

思路和组合中的二一样，只不过是判断条件略有不同，且其中判断重复的语句略有不同。

解题代码

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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        ArrayDeque<Integer> deque=new ArrayDeque<Integer>();
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        dfs(nums,deque,new boolean[nums.length],result);
        return result;
    }
    public void dfs(int[] nums,Deque<Integer> path,boolean[] used,List<List<Integer>> result){
        if(path.size()==nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]){
                continue;
            }
            //剪枝的过程中去重。
            //i>0&&nums[i-1]==nums[i]防止同一层出现重复，但是同一路径下的重复是被允许的。
            if(i>0&&nums[i-1]==nums[i]&&!used[i-1]){
                continue;
            }
            used[i]=true;
            path.addLast(nums[i]);
            dfs(nums,path,used,result);
            used[i]=false;
            path.removeLast();
        }
    }
}

78. 子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思想

这道题同样也是用了回溯算法，和上面的组合一样，我们可以将其拆分成从0到length-1长度的数组求其组合，最后得到的答案就是本题的答案。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        for(int i=0;i<=nums.length;i++){
            dfs(nums,i,new ArrayList<Integer>(),result,0);
        }
        return result;
    }

    public void dfs(int[]nums,int count,ArrayList<Integer> path,List<List<Integer>> result,int begin){
        if(path.size() == count){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        if(path.size() > count){
            return;
        }
        for(int i=begin;i<nums.length;i++){
            path.add(nums[i]);
            dfs(nums,count,path,result,i+1);
            path.remove((int)path.size()-1);
        }
    }
}
算法
#算法
回溯算法复习
https://dlddw.xyz/2022/07/01/回溯算法复习/
作者
Deepblue
发布于
2022年7月1日
许可协议