说明

回溯， 简单来说也就是暴力算法， 之前在学习二叉树 和 递归算法的时候， 我们都涉及到了回溯， 只是没有深究而已， 对于回溯而言，他本身就是将所有的结果穷举出来， 所以我们这里说回溯就是暴力算法。
在跟随《代码随想录》的学习中， 将回溯算法拆分为了以下几个模块来学习

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 棋盘问题：N皇后，解数独等等

也是通过上面的几种类型的题， 我们才能将回溯算法基本掌握， 但这并不代表完全掌握。所以下面我将按照上述几种类型的题型并结合我的力扣刷题没有AC的题目进行总结。

**解决回溯算法最好的方式就是画图将其抽象为树结构，然后根据图来进行理解 **
这是卡哥的回溯模板， 我们这里也是按照其进行代码书写的

1
2
3
4
5
6
7
8
9
10
11
12
public void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合问题

先来例题

77、 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
提示：

  • 1 <= n <= 20
  • 1 <= k <= n

思路

按照之前的思路， 就是将题抽象成为树结构
image.png
通过这种方式， 然后再结合卡哥的代码模板， 这样再来思考这道题，我个人是有种灵光一现的感觉。根据这个就写出了下面的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        get(n,k,1);
        return res;
    }
    public void get(int n , int k, int index){
    	//通过判断加入到集合中的数量来判断是否改加入这组path 到 res中
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        //从每层中取出index 之后的小于 n的数， 然后依次加入到集合中
        for(int i =index;  i<= n ; i++){
            path.add(i);
            get(n,k, i+1);
            path.remove(path.size() - 1);
        }
    }
}

好像我们就是根据代码模板填充参数一样， 但是第一次做这种类型的题我肯定是无法想出这种优质代码的。
但是这样的代码还不是最完美的。 因为他还是会有很多冗余的操作， 所以还需要枝减。

优化

以输入 n = 4， k = 4为例。 如果按照上面的思路来写， 我们肯定是要收集所有的，尽管后面的可能已经不满足了， 但是该走的路还是要走完。 这就是按照上面的代码写完的不足之处。
那么该如何枝减呢？
我们要收集的集合的内容是 k个
**集合中已经存在的是 **path.size()个
**还需要收集的是 **k- path.size()**个 **
列表中剩余元素（n-i）必须要 >= 所需需要的元素个数（k - path.size())
所以我们还需要收集的是 i <= n - (k - path.size()) + 1
理解上面的思路应该是很简单的，所以这样我们就可以省略很多不必要的遍历了。

image.png
这样一道题做出来看起来很简单， 但是我们想要实现的更加完美就显得困难了， 所以还需要自己对于回溯的理解更加透彻。

216、组合总和III

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

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

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

思路

本题相较于上道题题目上变化了很多， 但是真正思路上变化的只有一点， 就是排除解集中的重复项吗，
比如： k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] ,我们也许可以遍历得到[2,1,6],[6,1,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
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path= new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {

        combine(k,n,0,1);
        return res;
    }
    public void combine(int k ,int n, int sum , int index){
        if(path.size() == k){
            if(sum == n ){
                res.add(new ArrayList<>(path));
                return;
            }
        }
        // 优化内容  i <= 9 - (k- path.size()) +1;
        for(int i = index; i <= 9; i++){
            path.add(i);
            sum += i;
            combine(k,n,sum,i+1);
            sum -= i;
            path.remove(path.size() - 1);
        }
    }
}

17、 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png

示例 1：
输入：digits = “23” 输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：
输入：digits = “” 输出：[]
示例 3：
输入：digits = “2” 输出：[“a”,”b”,”c”]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

思路

这道题按照画图来理解， 其实就是 digits.length大小的集合， 然后集合中的每个数都进行一一组合， 然后将得到的结果封装起来返回。 改变点就是digits这个集合中每个内容的是映射到数字的不同符号而已。
所以按照我们得想法将其实现就可以得到下面得代码

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
class Solution {
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0 || digits == null) return res;‘
        //封装一组号码映射得集合
        String[] str = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        combine(digits, str, 0);
        return res;
    }

    StringBuilder st = new StringBuilder(); //可以高效的删除尾部
    public void combine(String digits, String[] str , int index){
        //终止条件
        if(index == digits.length()){
            res.add(st.toString());
            return;
        }
        //每次回溯得不同层，s就是每层得内容
        String s  = str[digits.charAt(index) - '0']; //可以直接转换为数字类型
        //回朔逻辑
        for(int i  =0 ;i < s.length(); i++){
            st.append(s.charAt(i));
            combine(digits, str, index + 1);
            //回朔
            st.deleteCharAt(st.length() - 1);
        }
    }
}

39、组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有_ _不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1 输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思路

这道题相较于前面两个组合总和不同点在于： 本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
**按照题目的要求 可以画出如下的树状结构图 **
image.png
candidates 中的 同一个 数字可以 无限制重复被选取就说明 在树状结构图中，下一层使用的数字不要筛减， 全部继承使用即可。
这样做的缺点就是如果target过大，那么这个树将会非常非常大。 所幸力扣给出的限制是 1 <= target <= 40
按照这样的思路得到的代码就如同下面。

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 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combine(candidates,target,0,0);
        return res;
    }
    public void combine(int []candidates, int target,int sum, int index){
        if(sum > target){
           return;
        }    
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i =index; i< candidates.length; i++){
            path.add(candidates[i]);
            sum += candidates[i];
            // 因为没有可以重复使用一个数， 所以不用 i+１
            combine(candidates, target,sum,i);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    
    }
}

40.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

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

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

思路

本题同样也是在上道题的思路上改进的,

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

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

通过着两个限制条件, 我们就需要重新规划刚才实现的回溯代码了.
**不仅在下一层回溯的时候需要 去除当前的元素, 给出的集合中还出现了重复的数字. **
此处就引出了我们的去重操作
这里有两重去重操作， 一种是使用 used数组， 另一种使用层序中的判断相等。 后者适合同层的数已经有序。 这里我们使用第二种。
image.png

得到的树状图就是上述的， 因为我们先对数组进行了排序， 排序不影响结果。 所以得到的同层内容就是有序的，可以通过使用if(i > index && candidates[i] == candidates[i-1]) continue; 来实现同层的去重， 同时需要更新当前层遍历过了的， 所以在递归的时候就需要combine(candidates, target, sum, i + 1); i+１　操作。
得到的代码就是

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
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        combine(candidates, target,0,0);
        return res;
    }
    public void combine(int[] candidates, int target, int sum , int index){
        if(sum >= target){
            if(sum == target){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        //

        for(int i = index; i < candidates.length ;  i++){
            //需要做去重操作
            if(i > index && candidates[i] == candidates[i-1]) continue;
            path.add(candidates[i]);
            sum  += candidates[i];
            combine(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

切割问题

通过上面的组合问题学习，对于回朔算法算是有一定程度的掌握了， 但是这并不是回溯算法的所有， 下面就是另一种题型， 切割问题

131、分割回文串

给你一个字符串 s，请你将_ s _分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例 1：
输入：s = “aab” 输出：[[“a”,”a”,”b”],[“aa”,”b”]]
示例 2：
输入：s = “a” 输出：[[“a”]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

思路

其实切割问题就是组合的一种形式， 本质上我认为还是通过不同字符串的组合， 看这个组合而成的字符串是否是回文串。 所以按照组合的形式理解也是可以的， 就看自己能不能将这种思想转换过来， 这种类型的题以切割的形式好理解， 所以我们是按照切割的形式来学习的。
抽象成为一个树形结构
image.png
这里就是在切割完的时候判断是否是回文串， 如果是在进行递归添加到集合中去， 如果不是， 那么就直接continue这个字符串， 换成和下一个字符串的组合，依次类推。
得到的代码就是

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
class Solution {
    List<List<String>>  res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {

        combine(s, 0);
        return res;
    }
    //可以使用String.reverse()来进行转换
    public void combine(String s , int index){
        if(index >= s.length() ){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i= index; i < s.length();i++ ){
            //判断字符串是否为回文串
            if(isReverse(s, index, i)){
                //获取他的子串
                String str = s.substring( index,i+ 1);
                path.add(str);
                combine(s, i + 1);
	            path.remove(path.size() - 1);
            }else{
                continue;
            }
            
        }        
    }

    public boolean isReverse(String str, int start, int end){
        for (int i = start, j = end; i < j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }

}

93、 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：”0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1“ 是 无效的 IP 地址。
示例 1：

  • 输入：s = “25525511135”
  • 输出：[“255.255.11.135”,”255.255.111.35”]

示例 2：

  • 输入：s = “0000”
  • 输出：[“0.0.0.0”]

示例 3：

  • 输入：s = “1111”
  • 输出：[“1.1.1.1”]

示例 4：

  • 输入：s = “010010”
  • 输出：[“0.10.0.10”,”0.100.1.0”]

示例 5：

  • 输入：s = “101023”
  • 输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]

提示：

  • 0 <= s.length <= 3000
  • s 仅由数字组成

思路

本题也是切割的一种，但是麻烦的是他也需要判断是否符合要求的操作，并且还需要进行拼接….
其余的基本一至。

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
45
46
47
48
49
50
51
52
class Solution {
    List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if(s.length() > 12) return res;
        combine(s, 0 , 0);
        return res;

    }
    public void combine(String s, int index, int point){
        if(point == 3){
            //检查最后一部分是否符合要求
            if(isValid(s, index, s.length() - 1)){
                //切割完成一组
                res.add(s);
                return;
            }
            return;
        }
        //单层检查是否符合要求
        for(int i = index ;i < s.length(); i++){
            //如果当前切割的符合要求
            if(isValid(s, index, i)){
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                point++;
                combine(s, i + 2, point); // 因为有小数点， 所以在回朔的时候需要进行加二
                //回朔
                point--;
                //删除其中的小数点
                s = s.substring(0 , i + 1) + s.substring(i + 2);
            }else{
                // 当前层不符合要求， 直接进行下一个的递归
                break;
            }
        }

    }
    //判断每个字符串是否符合要求
    public boolean isValid(String s, int start , int end) {
        if( start > end){
            return false;
        }
        // 1. 首先， 不能含有前导 0 
        if( end - start > 0 && s.charAt(start) == '0'){
            return false;
        }
        // 2. 其次 数字必须在0 - 255 之间
        String str = s.substring(start,end +1 );
        if(Integer.parseInt(str) > 255) return false;
        return true;
    }

}

90、 子集Ⅱ

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

  • 输入: [1,2,2]
  • 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

思路

子集问题其实就是之前总结的切割和组合的结合题.
但是本题需要进行去重， 给的数组有重复的元素， 但是要求解集不能有重复的子集…
也就是说相同的元素，在前面使用过了之后在后面就不能使用了。
这就是既需要在同层去重， 也需要在树枝上去重。 如图
image.png

我们通过使用排序， 将树枝去重的需求 改为了同层去重， 这样就不需要辅助数组了。 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
     List<List<Integer>> res = new ArrayList<>();
    List<Integer> path =  new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
       combine(nums, 0);
        return res;
    }
    public void combine(int []nums, int index){
        res.add(new ArrayList<>(path));

        for(int i =index; i < nums.length; i++){
            if(i > index && nums[i] == nums[i-1]) continue;
            path.add(nums[i]);
            combine(nums, i + 1);
            path.remove(path.size() - 1);
        }
        return;
    }
}

排列问题

通过上面的代码， 我们可以知道， 切割问题其实就是组合问题的一种， 但是表述和理解起来使用切割更符合人们的认知，所以就使用了切割，同时切割问题还有比较繁琐的一点就是需要判断切割的内容是否合乎要求。
排列问题就需要我们对不同要求的问题给出不同的筛选条件。就比如需要层序去重， 树枝去重等等….
下面就通过一些例题来学习排列问题。

46、 全排列

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

  • 输入: [1,2,3]
  • 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。
但排列问题需要一个used数组，标记已经选择的元素
used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

image.png

因为是全排列， 所以筛选条件就是path.size() == nums.length

得到的代码就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean []used = new boolean[nums.length];
        combine(nums,used);
        return res;
    }
    public void combine(int[] nums, boolean[] used){
        if(path.size() == nums.length ){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i =0; i < nums.length; i++){
            if(used[i] == true) continue;
            used[i] = true;
            path.add(nums[i]);
            combine(nums, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

47、 全排列2

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：

  • 输入：nums = [1,1,2]
  • 输出： [[1,1,2], [1,2,1], [2,1,1]]

示例 2：

  • 输入：nums = [1,2,3]
  • 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

思路

这道题目和46.全排列 的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。
所以这里需要进行去重， 我们这里还是通过使用排序，然后将去重的逻辑放到同层，并且还需要对树枝通过使用辅助数组used进行去重。
所以得到的代码如下

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
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        combine(nums,used);
        return res;
    }
    public void combine(int []nums, boolean[] used){
        if(path.size() == nums.length){
            // if(res.contains(path)) return;
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            //nums[i] == nums[i-1] 作用是判断是否同层的两个数相等
            //used[i] == false 是说明同层使用过
            //used[i] == true 是说明同树枝使用过 
            if(i> 0 && nums[i] == nums[i-1] && used[i-1] ==  false) continue;
            if(used[i] == true) continue;
            path.add(nums[i]);
            used[i] = true;
            combine(nums, used);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

参考说明

本文章是通过学习《代码随想录》总结而出， 一些图片因为自己画可能读者不太明白，所以就直接引用卡哥的图片了

所以推荐大家学习算法通过《代码随想录》地址: https://www.programmercarl.com/