【代码随想录】回溯

发表于 更新于 分类于 阅读次数： 本文字数： 11k 阅读时长 ≈ 36 分钟

回溯的基本理论

回溯是递归的产物。

回溯相当于穷举搜索。

回溯主要解决的问题：

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

回溯算法抽象为树形结构，回溯法解决的是在集合中递归寻找子集，集合的大小构成树的宽度，递归的深度就是树的深度。

回溯算法模板：

  • 回溯算法的返回值以及参数：返回值一般为void，但是参数需要根据逻辑来定。

    1
    void backtracking(参数)

  • 回溯算法终止条件：由于是树形结构，所以一般是搜索到叶子节点了，也就找到了满足条件的一个答案，将答案存储起来，结束本次递归。

    1
    2
    3
    4
    if (终止条件) {
        存放结果;
        return;
    }

  • 回溯搜索的遍历过程：在集合中搜索，集合的大小就是树的宽度，递归的深度就是树的深度

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

    for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

    backtracking这里自己调用自己，实现递归。

    大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

组合问题

题目：77

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路：

77.组合1

1.递归的参数和返回值：参数搜索范围[start, end]，注意是左闭右闭区间，以及k；同时使用一个全局变量记录已经搜索的路径。无返回值

2.递归的终止条件：当已经搜索的路径中大小等于k时，记录此时的路径并返回

3.递归的逻辑：本层的搜索范围是[start, end]，每次迭代将一个元素加入路径，然后递归，接着将这个元素从路径中删除

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:
    vector<vector<int>> result;
    vector<int> path;

    void BackTrace(int start, int end, int k) {
        // 判断是否应该终止
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        // 本层搜索范围
        for (int i = start; i <= end; i++) {
            path.push_back(i);
            BackTrace(i + 1, end, k);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        // 如果n小于k，那么递归能够正确返回
        BackTrace(1, n, k);

        return result;
    }
};

对于一个集合中的元素，无非取与不取两种状态，所以时间复杂度是O(2^n)；递归构建n种集合，所以总的时间复杂度是O(n*2n)

空间复杂度是O(n)，递归的栈空间。

剪枝优化

以n=4，k=4为例：
77.组合4

图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

注意代码中i，就是for循环里选择的起始位置。

接下来看一下优化过程如下：

  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+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
25
26
27
28
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;


    void backtracing(int n, int k, int start_index) {
        // 终止条件
        if (path.size() == k) {
            res.push_back(path);
            return;
        }

        // 循环处理集合
        // 这里的集合是[start_index, n]
        for (int i = start_index; i <= n - (k - path.size()) + 1; ++i) {
            path.push_back(i); // 加上当前结点
            backtracing(n, k, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        backtracing(n, k, 1);

        return res;
    }
};

组合总和III

题目：216

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

1.递归的参数和返回值：参数是搜索范围起始（终止一直都是9），以及还需要的值，k，另外需要一个全局变量保存结果，一个全局变量保存当前路径；无返回值

2.递归的终止条件：当前搜索路径中元素个数为k时，判断此时还需要的值是否为0，如果为0就保存结果，并返回。

3.递归的处理逻辑：遍历当前搜索范围，这里可以进行剪枝优化：当前路径的元素为 path.size()，还需要的元素个数为 k-path.size()，所以想要剩下的递归满足条件，搜索起点最多到end - (k-path.size()) + 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
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    
    // 回溯
    void BackTrace(int start, int k, int n) {
        // 终止条件
        if (path.size() == k) {
            if (n == 0) result.push_back(path);
            return;
        }

        // 剪枝优化搜索范围
        int end = 9 - (k - path.size()) + 1;
        // 本层搜索
        for (int i = start; i <= end; i++) {
            path.push_back(i);
            BackTrace(i + 1, k, n - i);
            path.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum3(int k, int n) {
        // 初始化
        // 略

        // 错误检查：如果都不符合能够完成递归
        // 范围检查：
        BackTrace(1, k, n);

        return result;
    }
};

时间复杂度为O(n*2^n)；空间复杂度O(n)

剪枝优化：

当path里面的总和大于n时，就可以不用再循环了。

电话号码的字母组合

题目：17

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

17

思路：每一个数字代表了一个搜索范围，因此数字的个数代表了搜索深度，每个数字代表的字符范围具有搜索宽度。

这里需要一个数组记录每个字符代表的搜索范围，使用hash表实现，(数字字符，对应的字符串)

搜索路径使用string的path表示。

1.递归的参数和返回值：字符串，当前搜素的字符下标，记录每个数字对应的搜索范围的hash表，令外使用一个全局变量path；无返回值

2.递归的终止条件：当前下标等于字符串长度时，记录此时的路径

3.递归的搜索逻辑：首先根据当前下标找到搜索范围，然后在搜索范围中进行搜索

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
class Solution {
public:
    vector<string> result;
    string path;

    // 回溯
    void Backtrace(string &digits, int index, unordered_map<char, string> &hash) {
        // 终止条件
        if (digits.size() == index) {
            // 记录此时的路径
            result.push_back(path);
            return;
        }

        // 确定本层的搜索字符串
        char c = digits[index];
        if (c < '2' || c > '9') exit(1);

        string target = hash[c];
        for (int i = 0; i < target.length(); i++) {
            path.push_back(target[i]);
            Backtrace(digits, index + 1, hash);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        // 初始化 略
        unordered_map<char, string> hash;
        // 初始化数字对应的字符串
        hash['2'] = "abc";
        hash['3'] = "def";
        hash['4'] = "ghi";
        hash['5'] = "jkl";
        hash['6'] = "mno";
        hash['7'] = "pqrs";
        hash['8'] = "tuv";
        hash['9'] = "wxyz";
        
        // 下面的操作要求至少一个元素
        if (digits.size() > 0)
            Backtrace(digits, 0, hash);

        return result;
    }
};

时间复杂度: O(3^m * 4^n)，其中 m 是对应四个字母的数字个数，n 是对应三个字母的数字个数

阶段总结1

回溯就是暴力搜索。

回溯算法的整体思想：看作是对于树结构的操作，for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

横向搜索当前范围集合，纵向取出元素时候搜索新的范围集合。组合问题、组合总和III、电话号码思路基本一致。

回溯算法剪枝：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够 题目要求的k个元素了，就没有必要搜索了。

组合总和

题目：第39题

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

分析：

之前遇到的组合问题每个元素只能选择一次，这里的元素可以重复选取。因此每一层递归的搜索范围都是candidates。这样就有可能出现重复组合，为了避免重复下一层递归的范围只能从当前下标开始，这样保证了同一个元素可以选择多次，后出现的元素也不会再与前面的元素重新配对。

1.递归的参数和返回值：参数是候选数组，以及当前搜索范围起点，目标整数，另外需要一个全局变量记录结果，一个全局变量记录路径；无返回值

2.递归的终止条件：由于这里的每个整数都是大于0的，那么当剩余整数刚好等于0是记录组合并返回；如果剩余整数值小于0也返回。

3.递归的处理逻辑：对当前范围进行搜索，这里递归下一层时搜索范围注意起点。

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 {
public:
    vector<vector<int>> result;
    vector<int> path;

    void BackTrace(vector<int> &candidates, int start, int target) {
        // 终止条件
        if (target == 0) {
            result.push_back(path);
            return;
        } else if (target < 0) return;

        // 搜索本层
        for (int i = start; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            BackTrace(candidates, i, target - candidates[i]); // 下一层递归的范围从当前元素开始
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // 如果没有元素会一直递归
        // 所以不能为空
        if (candidates.size() != 0)
            BackTrace(candidates, 0, target);
        return result; 
    }
};

剪枝：先对待选集合进行升序排列，那么当出现加上一个集合中的元素超过target时就可以直接终止本层循环（横向）。

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void BackTrace(vector<int> &candidates, int start, int target) {
        // 终止条件
        if (target == 0) {
            result.push_back(path);
            return;
        } else if (target < 0) return;

        // 搜索本层
        for (int i = start; i < candidates.size(); i++) {
            // 剪枝：此时候选数组已经升序排列
            // 如果加上当前元素就已经大于target
            // 那么本层不需要再递归
            if (target - candidates[i] < 0) break;

            path.push_back(candidates[i]);
            BackTrace(candidates, i, target - candidates[i]); // 下一层递归的范围从当前元素开始
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // 如果没有元素会一直递归
        // 所以不能为空
        if (candidates.size() != 0) {
            // 排序，为剪枝做准备
            sort(candidates.begin(), candidates.end());

            BackTrace(candidates, 0, target);
        }
            
        return result; 
    }
};

时间复杂度: O(n * 2^n)，注意这只是复杂度的上界，因为剪枝的存在，真实的时间复杂度远小于此

组合总和II

题目：40题

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

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

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

分析：

这一题与上一题的区别是，里面的元素有可能重复，另外每个元素只能使用一次。

每个元素只能使用一次就意味着本层递归使用过的下标，下一层就不能使用。

里面的元素有可能重复，这意味着如果在同一层递归中，那么相同的多个元素只需要一个进入下一层递归。因此先排序，保证相同的元素都挨着，在同一层递归中如果与上一个元素相同，那么就不进行递归。

40.组合总和ii

1.递归的参数和返回值：参数是候选数组，搜索起点下标，全局变量：路径和，路径，结果；无返回值

2.递归的终止条件：如果路径和等于目标，那么记录路径；如果路径和大于目标则返回；

3.递归的处理逻辑：在搜索范围中迭代时，首先判断与上一个元素是否相同，相同就跳过；然后进行递归与回溯。

剪枝：如果当前值加入之后路径和已经大于目标值，那么本层后序的迭代无需进行。

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int sum;

    void BackTrace(vector<int> &candidates, int start, int target) {
        // 递归终止条件
        if (sum == target) {
            result.push_back(path);
            return;
        } else if (sum > target) {
            return;
        }

        // 单层逻辑
        for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // 如果当前值与本层上一个值相同则无需递归
            if (i > start && candidates[i] == candidates[i - 1]) continue;

            path.push_back(candidates[i]);
            sum += candidates[i];
            BackTrace(candidates, i + 1, target);
            sum -= candidates[i];
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // 初始化
        sum = 0;
        // 候选数组个数不能为0
        if (candidates.size() == 0) exit(1);

        // 排序，为避免重复做准备
        sort(candidates.begin(), candidates.end());
        BackTrace(candidates, 0, target);

        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

分割回文串*

题目：131

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

分析：

定义分割点：例如对于aab，分割点1表示 a | ab，这样可以将字符串分割成两段。

每层的搜索范围有一个起点start，然后分别设置不同的分割点，从起点到分割点，可以构成一个子串，如果这个子串是一个回文串，就可以将其加入划分方案，并接着从后面进行递归。

例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。

所以切割问题，也可以抽象为一棵树形结构，如图：

131.分割回文串

首先要有一个判断是否是回文的函数 IsPalin

1.递归的参数和返回值：参数是字符串，起点，另外需要一个全局变量记录答案和记录当前分割方案；无返回值

2.递归的终止条件：当起点就是字符串的长度时，应该记录此时的分割方案

3.递归的处理逻辑：从起点开始，向后的分割字符数从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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;

    // 判断是否为回文串
    bool IsPalin(const string &s) {
        if (s.length() == 0) return true;

        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }

        return true;
    }

    void BackTrace(string &s, int start) {
        // 递归终止条件
        if (start == s.length()) {
            result.push_back(path);
            return;
        }

        // 单层逻辑
        for (int i = 1; start + i <= s.length(); i++) {
            // 首先切割出一个子串
            string tmp = s.substr(start, i);
            // 判断这个子串是否为回文
            if (!IsPalin(tmp)) continue;

            path.push_back(tmp);
            BackTrace(s, start + i);
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        // 空字符串可以递归
        BackTrace(s, 0);

        return result;
    }
};

优化：待补充

复原IP地址

题目：93

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

分析：同样是切割问题，切割出来的整数最长为3个。并且切割出来的字符串必须合法：不能有前导0、范围必须是0到255之间。

深度是4，宽度是从当前起始范围向后3个。

首先需要一个判断切割出来的字符串是否合法的函数：

如果长度等于1，怎么都是合法的；

如果长度大于1，如果第一位是0，那么就是不合法的（如果后面数字不管是0还是其它都不合法）；如果使用stoi转化之后范围超过255也是不合法的（一定是大于0的）

1
2
3
4
5
6
7
8
9
// 判断字符串是否符合ip地址某一部分有效要求
bool IsValid(const string &s) {
    // 范围检查
    if (s.size() == 0 || s.size() > 3) exit(1);

    if (s.size() == 1) return true;
    else if (s[0] == '0' || stoi(s) > 255) return false;
    else return true;
}

1.递归的参数和返回值：参数是字符串，起始范围，另外使用全局变量记录结果和切割方案；无返回值

2.递归的终止条件：当前切割方案中元素为4终止，如果开始范围为字符串长度时则记录切割方案，否则不记录。

3.递归的处理逻辑：每层从开始范围向后迭代三个作为一段，如果后面不足三个则截至结尾。

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
53
54
55
56
class Solution {
public:
    enum { MaxWidth = 3, MaxDepth = 4 };
    vector<string> result;
    vector<int> path;

    // 判断字符串是否符合ip地址某一部分有效要求
    bool IsValid(const string &s) {
        // 范围检查
        if (s.size() == 0 || s.size() > 3) exit(1);

        if (s.size() == 1) return true;
        else if (s[0] == '0' || stoi(s) > 255) return false;
        else return true;
    }

    void Backtrace(const string &s, int start) {
        // 终止条件
        if (path.size() == MaxDepth) {
            // 如果当前起始范围到达字符串末尾
            if (start == s.length()) {
                // 将path转换成string
                string tmp;
                for (int x : path) {
                    tmp += to_string(x);
                    tmp += ".";
                }
                // 删除最后一个分割点
                tmp.pop_back();
                result.push_back(tmp);
            }

            return;
        }

        // 单层处理逻辑
        for (int i = 1; i <= MaxWidth && start + i <= s.length(); i++) {
            // 切割字符串
            string tmp = s.substr(start, i);
            // 如果不合法本层递归结束
            if (!IsValid(tmp)) break;

            path.push_back(stoi(tmp));
            Backtrace(s, start + i);
            path.pop_back();
        }

    }

    vector<string> restoreIpAddresses(string s) {
        // 空字符串可以递归
        Backtrace(s, 0);

        return result;
    }
};
  • 时间复杂度: O(3^4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式，则搜索树的最大深度为4，每个节点最多有3个子节点。
  • 空间复杂度: O(n)

子集

题目：78

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

分析：

求子集，在递归搜索上的每一个路径都可以作为子集

78.子集

每个元素各不相同意味着不用担心去重，下一层的迭代从上一层迭代范围的后面开始即可。

1.递归的参数和返回值：参数是数组，起始范围，另外需要全局变量记录结果和搜索路径；无返回值

2.递归的终止条件：当起始范围等于数组长度时终止

3.递归的处理逻辑：每一层递归开始时首先将路径保存在结果中；然后判断是否应该终止；最后对本层范围进行搜索

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:
    vector<vector<int>> result;
    vector<int> path;

    void BackTrace(const vector<int> &nums, int start) {
        // 首先将路径添加进结果
        result.push_back(path);

        // 递归终止条件
        if (nums.size() == start) return;

        // 本层搜索
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            BackTrace(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        // 初始化
        // 递归时会自动添加一个空集
        BackTrace(nums, 0);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

阶段总结2

组合总和：主要是考虑集合中的元素可以重复使用，那么在递归时就不需要将start_index加1；另外这里可以采取排序之后剪枝的操作。

组合总和II：这里主要是集合元素中会有重复。因此在本层中如果已经遍历过相同元素，本层无需再次遍历。这里需要使用排序将相同的元素凑在一起。

分割回文串：使用求解组合问题的思路来解决切割问题，将切割的下标作为递归参数传递。

复原IP地址：同样是将切割问题看作是组合问题。

求解子集：搜索路径上的每一个状态都是结果。

子集II（全排列如何处理）

题目：90

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

分析：这一题同样是每个元素只使用一次，采用递归，路径的每一个状态都是结果。

这一题与上一题不同的是：可能存在重读元素，所以在同一层遍历时，相同元素只需遍历一次。这里采排序的方法，将相同元素凑在一起。

1.递归的参数和返回值：参数是排序完成的数组，以及开始范围，另外需要全局变量记录结果和路径；无返回值

2.递归的终止条件：当起始范围等于数组长度时返回

3.递归的逻辑：每层开始时首先将路径添加；然后判断是否终止；最后在本层迭代，本层迭代时需要注意，如果当前元素与前一个元素相同就无需再遍历。

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void BackTrace(const vector<int> &nums, int start) {
        // 保存当前路径状态
        result.push_back(path);

        // 终止条件
        if (nums.size() == start) return;

        // 本层搜索逻辑
        for (int i = start; i < nums.size(); i++) {
            // 重复元素不重复处理
            if (i > start && nums[i] == nums[i - 1]) continue;

            path.push_back(nums[i]);
            BackTrace(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // 排序，为去重做准备
        sort(nums.begin(), nums.end());
        // 范围检查：空数组可以进入递归
        BackTrace(nums, 0);

        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

另外还可以使用set去重。

全排列：如果要是全排列的话，每次要从0开始遍历，为了跳过已记录的元素，需要使用used。

递增子序列

题目：491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

分析：

然后每个元素只能使用一次，所以下一层的递归范围应该时本层的范围向后一位。

数组中可能会有重复元素，但是允许两个相同元素在一个集合里，这个意思是，同一个深度上，允许两个相同元素，但是在同一层上，相同元素需要去重。

491. 递增子序列1

所以这里引入used数组，在同一层上，如果当前元素曾经使用过，那么本层就不能再使用。

1.递归的参数和返回值；参数是数组，搜索范围起点，另外需要全局变量记录答案和路径；无返回值

2.递归的终止条件：如果当前起始范围是数组长度则返回

3.递归的处理逻辑：每层递归开始首先判断path长度是否大于等于2，如果是则保存进结果；然后判断是否终止；接着使用一个unordered_set记录当前层范围内使用情况，当一个元素与前一个元素相同时，只有前一个元素已经使用过才能使用当前元素。

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void BackTrace(const vector<int> &nums, int start) {
        // 记录结果
        if (path.size() > 1) result.push_back(path);

        // 递归终止
        if (nums.size() == start) return;

        // 一个set记录曾经使用过的元素
        unordered_set<int> used;
        for (int i = start; i < nums.size(); i++) {
            // 取出当前元素
            int x = nums[i];
            // 如果已经在集合中则说明已经使用过
            // 本层不能再使用
            if (used.find(x) != used.end()) continue;

            // 判断是否比路径尾部元素大
            if (path.empty() || x >= path.back()) {
                path.push_back(x);
                used.insert(x); // 标记本层已经使用过
                BackTrace(nums, i + 1);
                path.pop_back();
            }
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        // 范围检查：空数组可以进入递归
        BackTrace(nums, 0);

        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

全排列

题目：46

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

分析：由于是全排列，所以每层的搜索范围都是这个数组；但是又不能重复使用同一个数字，所以需要一个used数组记录使用情况，只有未被使用的数字才能遍历。

46.全排列

由于没有重复元素，所以不用担心重复问题。

1.递归的参数和返回值：参数是数组，另外需要全局变量记录路径和结果、使用情况；无返回值

2.递归的终止：当路径中的元素已经等于数组大小时，记录结果并返回

3.递归的处理逻辑：遍历本层范围，只有未被使用的元素才能遍历。

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used;

    void BackTrace(const vector<int> &nums) {
        // 递归终止
        if (nums.size() == path.size()) {
            result.push_back(path);
            return;
        }

        // 本层搜索
        for (int i = 0; i < nums.size(); i++) {
            // 只有当前元素未被使用过才可以遍历
            if (true == used[i]) continue;

            path.push_back(nums[i]);
            used[i] = true; // 标记已被使用
            BackTrace(nums);
            used[i] = false; // 消除标记
            path.pop_back();
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        // 范围检查：空数组不要进入递归，因为会添加一个空路径
        if (nums.size() == 0) return result;
        
        // 初始化
        used = vector<bool>(nums.size(), false);

        BackTrace(nums);

        return result;
    }
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n)

全排列II

题目：47

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

分析：本题与上一题的区别就是本题可以存在重复数字。

允许在同一根树枝上存在重复元素，即在深度上、搜索路径上可以存在重复元素；但是不能在同一层上存在重复元素，这因为重读元素已经作为该层被使用了。

47.全排列II2

层去重需要对数组进行排序。如果当前元素与前一个元素相同并且前一个元素已经被使用过，说明二者在同一个深度上，此时可以遍历；如果当前元素与前一个元素相同但是前一个元素没有被使用，说明二者在同一个宽度上，此时不能遍历。

1.递归的参数和返回值：参数是排序的数组，另外需要全局变量记录结果、路径、used；无返回值

2.递归的终止条件：当path中的个数等于数组大小时，记录结果并返回

3.递归的处理逻辑：对于每一个元素，当与前者相同时，如果前者已经被使用，则可以遍历；否则不能遍历。

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
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<bool> used;

    void Backtrace(const vector<int> &nums) {
        // 终止条件
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        // 本层搜索
        for (int i = 0; i < nums.size(); i++) {
            // 判断当前元素是否重复
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            // 判断当前元素是否使用过
            if (!(used[i])) {
                path.push_back(nums[i]);
                used[i] = true;
                Backtrace(nums);
                used[i] = false;
                path.pop_back();
            }
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        // 范围检查：空数组不能进入递归
        if (nums.size() == 0) return result;

        // 初始化
        used = vector<bool>(nums.size(), false);

        Backtrace(nums);

        return result;
    }
};
  • 时间复杂度: O(n! * n)
  • 空间复杂度: O(n)

拓展

大家发现，去重最为关键的代码为：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

**如果改成 used[i - 1] == true， 也是正确的!**，去重代码如下：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

这么说是不是有点抽象？

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)，的树形结构如上图，

树枝上去重（used[i - 1] == true）的树型结构如下：

47.全排列II3

大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。

阶段总结3（性能分析）

求子集II：排序之后去重（同层去重）

递增子序列：没有排序，但是需要在每一层遍历中判断同一个父节点只能使用剩余集合中的相同元素一次。（同层去重）

排列1：与组合不同的是每次遍历和集合都是全集，所以需要判断这个元素是否之前已经使用过（全局去重）

排列2：与上一题相比全集中会有重复元素，所以排列之后判断相同元素是否在同一层使用过；同时由于遍历全集，即使与前面元素不同，还需要判断路径上是否已经使用过这个元素。（全局去重 + 同层去重）

性能分析：

子集问题分析：

  • 时间复杂度：$O(n × 2^n)$，因为每一个元素的状态无外乎取与不取，所以时间复杂度为$O(2^n)$，构造每一组子集都需要填进数组，又有需要$O(n)$，最终时间复杂度：$O(n × 2^n)$。
  • 空间复杂度：$O(n)$，递归深度为n，所以系统栈所用空间为$O(n)$，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$。

排列问题分析：

  • 时间复杂度：$O(n!)$，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ….. 1 = n!。每个叶子节点都会有一个构造全排列填进数组的操作（对应的代码：result.push_back(path)），该操作的复杂度为$O(n)$。所以，最终时间复杂度为：n * n!，简化为$O(n!)$。
  • 空间复杂度：$O(n)$，和子集问题同理。

组合问题分析：

  • 时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
  • 空间复杂度：$O(n)$，和子集问题同理。

一般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是一个概括

重新安排行程

题目：332

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

分析：

处在某一个机场，下一步的搜索范围是有限的，但是必须按照字典序走下一个机场。可以使用一个无序map保存（当前机场，下一步可走范围），这里的下一步可走范围需要是有序的，所以可以使用有序map实现，有序map底层是红黑树，是一种二叉搜索树，能够按照key的顺序从小到大排列，所以遍历有序map就是从小到大遍历可走的所有机场。

1.递归的参数和返回值：参数是无序map表示的（当前机场，下一步可走机场）；另外需要全局变量记录答案；无返回值是bool，这是因为当找到第一条合适的路径时就应该立即返回，不能再递归，否则记录的就是最后一条满足的路径。

2.递归的终止条件：当路径中个数等于票总数+1时返回

3.单层逻辑：找到当前机场下一步范围，只有当下一步可用次数大于0时才能遍历。

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
class Solution {
public:
    unordered_map<string, map<string, int>> targets;

    bool BackTrace(const int tickets_num, vector<string> &result) {
        // 终止条件
        if (result.size() == tickets_num + 1) return true;

        // 单层处理逻辑
        string start = result.back();
        for (pair<const string, int> &target : targets[start]) {
            // 当票数大于0时
            if (target.second > 0) {
                result.push_back(target.first);
                target.second--;
                
                // 当找到一条路径时
                if (BackTrace(tickets_num, result)) return true;

                result.pop_back();
                target.second++;
            }
        } 

        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> result;

        // 记录票数
        for (const vector<string> &vec : tickets) 
            targets[vec[0]][vec[1]]++;

        result.push_back("JFK");
        BackTrace(tickets.size(), result);

        return result;
    }
};

如果单纯的回溯搜索（深搜）并不难，难还难在容器的选择和使用上。

本题其实是一道深度优先搜索的题目，但是我完全使用回溯法的思路来讲解这道题题目，算是给大家拓展一下思维方式，其实深搜和回溯也是分不开的，毕竟最终都是用递归。

N皇后

题目：51

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

分析：

一共需要选择n行的位置，每一行的可选范围收到之前位置的制约。因此递归深度是n，递归的宽度需要已经放置的棋子来确定。

假如当前需要放置的位置是(r, c)，那么需要一个函数判断是否合法：

（1）同行不需要判断，因此没次递归行数都需要增加；

（2）同列需要判断：判断在[0 ~ r-1]，c位置上是否已经存在皇后

（3）左上斜线需要判断

（4）右上斜线需要判断

1.递归的参数和返回值：参数是n，本层处理第row行，以及全局变量记录答案和当前放置情况；无返回值

2.递归的终止条件：row的范围是[0, n-1]，所以当row==n时记录结果并退出

3.递归的处理逻辑：遍历本行可处理范围，如果放置位置合法则遍历。

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
53
54
55
56
class Solution {
public:
    vector<vector<string>> result;
    vector<string> board;

    // 判断将皇后放在(row, col)是否合法
    bool IsValid(int row, int col) {
        // 首先判断同列上是否存在皇后
        for (int r = row - 1; r >= 0; r--) {
            if (board[r][col] == 'Q') return false;
        }

        // 判断左上斜线是否存在皇后
        for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) {
            if (board[r][c] == 'Q') return false;
        }

        // 判断右上斜线是否存在皇后
        for (int r = row - 1, c = col + 1; r >= 0 && c < board[0].size(); r--, c++) {
            if (board[r][c] == 'Q') return false;
        }

        return true;
    }

    void BackTrace(int n, int row) {
        // 递归终止条件
        if (n == row) {
            result.push_back(board);
            return;
        }

        // 本层搜索逻辑
        for (int col = 0; col < n; col++) {
            // 只有当前插入点合法时才能继续遍历
            if (IsValid(row, col)) {
                // 将皇后插入
                board[row][col] = 'Q';
                BackTrace(n, row + 1);
                board[row][col] = '.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        // 范围检查：n不可以为0
        if (n == 0) exit(-1);
        
        // 初始化
        board = vector<string>(n, string(n, '.'));

        BackTrace(n, 0);

        return result;
    }
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n)

解数独

题目：37

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

37

1
2
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

37-1

分析：

每层递归处理一行row中为’.’的字符，可填写的范围是1~9；需要判断填入之后是否合法：

（1）判断同一行中是否已经存在该元素；

（2）判断同一列中是否已经存在该元素；

（3）判断以实线分割的范围内是否存在该元素：假设当前下标为(row, col)，搜索范围是：行：[int(row / 3)*3, +3)。列[int(col / 3) 3, +3)。例如对于(2, 7)，搜索的行范围应该是[0, 3)，列范围应该是[6, 9)

然后使用递归+回溯的方法完成搜素。

1.递归的参数和返回值：参数是board和；由于答案唯一，因此如果已经找到答案立即返回true

2.递归的终止条件：

3.递归的处理逻辑：遍历本层行列，找到为’.’的元素，使用1~9填充，判断填充合法之后就可以记录递归。

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
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    // 判断将元素插入到(row, col)是否合法
    bool IsValid(vector<vector<char>> &board, char target, int row, int col) {
        // 判断同行是否存在target
        for (int c = 0; c < board[0].size(); c++) {
            if (board[row][c] == target) return false;
        }

        // 判断同列是否存在target
        for (int r = 0; r < board.size(); r++) {
            if (board[r][col] == target) return false;
        }

        // 判断所属3X3范围是否存在target
        // 计算左闭右开区间
        int r_start = int(row / 3) * 3;
        int r_end = r_start + 3;
        int c_start = int (col / 3) * 3;
        int c_end = c_start + 3;
        for (int r = r_start; r < r_end; r++) {
            for (int c = c_start; c < c_end; c++) {
                if (board[r][c] == target) return false;
            }
        }

        return true;
    }

    bool BackTrace(vector<vector<char>> &board) {
        int m = board.size();
        int n = board[0].size();
        // 遍历二维数组找到值为.的元素
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] != '.') continue;

                // 如果当前元素是.则尝试填入
                for (char target = '1'; target <= '9'; target++) {
                    // 如果插入位置合法
                    if (IsValid(board, target, r, c)) {
                        board[r][c] = target;
                        if (BackTrace(board)) return true;
                        board[r][c] = '.';
                    }
                } // end for target
                // 如果尝试插入1~9都失败
                // 那么立即返回，不可能存在答案
                return false;                
            } // end for c
        } // end for r

        // 如果循环中都没退出
        // 说明所有.都已经被替换
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        // 范围检查
        if (board.size() != 9 || board[0].size() != 9) exit(-1);

        BackTrace(board);
    }
};

阶段总结4

重新安排行程：难点主要在于使用什么容器保存下一次需要遍历的范围，以及找到之后立即返回；

N皇后：难点主要在于判断插入之后是否合法；

解数独：难点主要在于判断插入之后是否合法。

回溯总结

回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解决如下问题：

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

回溯法的模板：

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

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