五、回溯（trackback）

一、算法定义

抽象地说，解决一个回溯问题，实际上就是遍历一棵决策树的过程，树的每个叶子节点存放着一个合法答案。你把整棵树遍历一遍，把叶子节点上的答案都收集起来，就能得到所有的合法答案。
站在回溯树的一个节点上，你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。

二、经典例题

（一）排列

1.46.全排列

（1）思路

（2）代码

class Solution {
public:
vector<vector<int>> res;
    void dfs(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(),false);
        trackback(nums,path,used);
    }
    void trackback(vector<int>& nums,vector<int>&path,vector<bool>&used) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return ;
        }
        for (int i = 0; i < nums.size(); i ++) {
            if (used[i] == true) continue;
            path.push_back(nums[i]);
            used[i] = true;
            trackback(nums, path, used);
            used[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.size() == 0) return res;
        dfs(nums);
        return res;
    }
};
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

（3）复杂度分析

时间复杂度：O(n x n!)
空间复杂度：O(n),其中n为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)。

2.LCR 083. 全排列

（1）思路

（2）代码

class Solution {
public:
vector<vector<int>> res;
    void process(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(),false);
        dfs(used,path,nums);

    }
    void dfs(vector<bool>& used,vector<int> &path,vector<int>& nums) {
        if (path.size() == nums.size())
        {

            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            path.push_back(nums[i]);
            used[i] = true;
            dfs(used,path,nums);
            used[i] = false;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.size() == 0) return res;
        sort(nums.begin(),nums.end());
        process(nums);

        return res;
    }
};
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

（3）复杂度分析

时间复杂度：O(n x n!)
空间复杂度：O(n)

3.46.全排列2

（1）思路

（2）代码

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
    void process(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        trackback(nums,used);
        
    }
    void trackback(vector<int>& nums,vector<bool>& used) {
        if (path.size() == nums.size()) {
            res.push_back(path); 
            return; 
        }
        for (int i = 0; i < nums.size(); i ++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
            if (used[i] == false) {
            path.push_back(nums[i]);
            used[i] = true;
            trackback(nums, used);
            path.pop_back();
            used[i] = false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if (nums.size() == 0) return res;
        sort(nums.begin(),nums.end());
        process(nums);
        return res;
    }
};
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

（3）复杂度分析

// 时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组
// 空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素

（二）组合

1.77.组合

（1）思路

前序位置，每个节点的值都是一个子集。

（2）代码

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
    void trackback(int n,int k,int start) {
        if (path.size() == k) {
            res.push_back(vector<int>(path.begin(), path.end()));
            return ;
        }
        for (int i = start;i <= n; i++) {
            path.push_back(i);
            trackback(n, k, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        if(n == 0) return res;
        trackback(n,k,1);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.39.组合总和

（1）思路

（2）代码

class Solution {
public:
vector<vector<int>>res;
vector<int> path;
    void backtrack(vector<int>& candidates,int target,int sum,int start) {
        if (sum == target) {
            res.push_back(path);
            return ;
        }
        for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++) {
        
            
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtrack(candidates, target, sum,i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if (candidates.size() == 0) return res;
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtrack(candidates,target,0,0);    
        return res;
    }

};
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

（3）复杂度分析

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

3.40.组合总和2

（1）思路

（2）代码

class Solution {
public:
vector<vector<int>> res;
vector<int> path;

    void trackback(vector<int>& candidates, int target,int sum,int start,vector<bool> &used) {
        if (sum == target) {res.push_back(path);return;}
        for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
        
            sum += candidates[i];
            used[i] = true;
            path.push_back(candidates[i]);
            trackback(candidates, target, sum, i + 1,used);
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if (candidates.size() == 0) return res;
        vector<bool> used(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        trackback(candidates,target,0,0,used);
        return res;
    }
};
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

（3）复杂度分析

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

4.216.组合总和3

（1）思路

（2）代码

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
    void trackback(int k,int n,int index,int sum) {
        if (path.size() == k) {
            if (sum == n) res.push_back(path);
            return ;
        }
        for (int i = index; i <= 9 -(k - path.size()) + 1; i++) {
            sum += i;
            path.push_back(i);
            if (sum > n) {
                sum -= i;
                path.pop_back();
                return ;
            }
            trackback(k, n, i + 1,sum);
            path.pop_back();
            sum -= i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        if (n == 0) return res;
        trackback(k,n,1,0);
        return res;
    }
};
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

5.17.电话号码的字母组合

（1）思路

（2）代码

class Solution {
public:
const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
};
vector<string> result;
string s;
    void backtracking(const string  &digits,int index) {
        if (index == digits.size()) {
            result.push_back(s);
            return ;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);

            backtracking(digits, index + 1);
            s.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};
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

（3）复杂度分析

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

（三）子集

1.78.子集

（1）思路

还是以 nums = [1,2,3] 为例，刚才让你求所有子集，就是把所有节点的值都收集起来；现在你只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合。

（2）代码

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums,0);
        return res;
    }
    void backtrack(vector<int>& nums,int start) {
        res.push_back(path);

        for (int i = start; i < nums.size(); i ++) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1);
            path.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（3）复杂度分析

时间复杂度：O(n×2n)。一共 2n个状态，每种状态需要 O(n)的时间来构造子集。
空间复杂度：O(n)，临时数组 t 的空间代价是 O(n），递归时栈空间的代价为 O(n)。

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
    void trackback(int n,int k,int start) {
        if (path.size() == k) {
            res.push_back(vector<int>(path.begin(), path.end()));
            return ;
        }
        for (int i = start;i <= n; i++) {
            path.push_back(i);
            trackback(n, k, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        if(n == 0) return res;
        trackback(n,k,1);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.131.分割回文串

（1）思路

切割问题，有不同的切割方式
判断回文

（2）代码

class Solution {
public:
vector<vector<string>> res;
vector<string> path;
    void backtrack(string s,int start) {
        if (start >= s.size()) { // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
            res.push_back(path);
            return ;
        }   
        for (int i = start; i < s.size(); i ++) {
            if (isVaild(s,start,i)) {
                string str = s.substr(start,i - start + 1);
                path.push_back(str);
            }
            else {
                continue;
            }
            backtrack(s, i + 1); // 寻找i+1为起始位置的子串
            path.pop_back();
        }
      
    }
    bool isVaild(const string& s, int start, int end) {
     for (int i = start, j = end; i < j; i++, j--) {
         if (s[i] != s[j]) {
             return false;
         }
     }
     return true;
 }
    vector<vector<string>> partition(string s) {
        if (s.size() == 0) return res;
        backtrack(s,0);
        return res;
    }
};
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

（3）复杂度分析

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

class Solution {
public: 
vector<string> res;
string path;
    void backtrack(string &s,int start,int pointSum) {
        if (pointSum == 3) {
            if (inVaild(s,start, s.size() - 1)) {
                res.push_back(s);
            }
            return ;
        }
        for (int i = start;i < s.size(); i++) {
            if (inVaild(s,start,i)) {
                 s.insert(s.begin() + i + 1 , '.');
                 pointSum ++;
                 backtrack(s, i + 2, pointSum);
                 pointSum --;
                 s.erase(s.begin() + i + 1);      
            }
            else  break;
        }
    }
    bool inVaild(const string & s,int start,int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) {
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') {
            return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255)
                return false;
            }   
       return true;
    }   
    vector<string> restoreIpAddresses(string s) {
        if (s.size() == 0) return res;
        backtrack(s,0,0);
        return res;
    }
};
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

3.93.复原IP地址

（1）思路

（2）代码

class Solution {
public: 
vector<string> res;
string path;
    void backtrack(string &s,int start,int pointSum) {
        if (pointSum == 3) {
            if (inVaild(s,start, s.size() - 1)) {
                res.push_back(s);
            }
            return ;
        }
        for (int i = start;i < s.size(); i++) {
            if (inVaild(s,start,i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                 s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
                 pointSum ++;
                 backtrack(s, i + 2, pointSum); //  插入逗点之后下一个子串的起始位置为i+2
                 pointSum --;
                 s.erase(s.begin() + i + 1);    //回溯删掉逗点
            }
            else  break;
        }
    }
    bool inVaild(const string & s,int start,int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) {
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') {
            return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255)
                return false;
            }   
       return true;
    }   
    vector<string> restoreIpAddresses(string s) {
        if (s.size() == 0) return res;
        backtrack(s,0,0);
        return res;
    }
};
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

（3）复杂度分析

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

4.90.子集 II

（1）思路

（2）代码

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
 void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
     res.push_back(path);
     for (int i = startIndex; i < nums.size(); i++) {
          if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop_back();
     }
}
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0, used);
        return res;
    }
};
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

（3）复杂度分析

• 时间复杂度: O(n * 2^n)
• 空间复杂度: O(n)

5.491.递增子序列

class Solution {
public:
vector<vector<int>> res;
vector<int> path;
    void backtrack(vector<int>&nums,int start) {
        if (path.size() > 1) {
            res.push_back(path);
    // 注意这里不要加return，因为要取树上的所有节点
        }
        unordered_set<int> uset; // 使用set对本层元素进行去重
        for (int i = start; i < nums.size(); i ++ ) {
            if ((!path.empty() && nums[i] < path.back())
                    || uset.find(nums[i]) != uset.end()) {
                    continue;
            }
            uset.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
            path.push_back(nums[i]);
            backtrack(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        if (nums.size() == 0) return res;
        
        backtrack(nums,0);
        return res;
    }
};
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

（四）N皇后问题、岛屿问题

1.51.N皇后

（1）思路

（2）代码

class Solution {
public:
vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board (n,string(n,'.'));
        backtrack(board,0);
        return res;
    }
    void backtrack(vector<string>& board, int row) {
        if (row == board.size()) {
            res.push_back(board);
            return;
        }
        int n = board[row].size();
        for (int col = 0; col < n; col++) {
            if (!isvaild(board,row,col)) {
                continue;
            }
            board[row][col] = 'Q';
             backtrack(board, row + 1);
            // 撤销选择
            board[row][col] = '.';
        }
    }
    bool isvaild(vector<string>& board, int row, int col) {
        int n = board.size();
        for (int i = 0; i <= row; i++) {
            if (board[i][col] == 'Q')
                return false;
        }
        for (int i = row - 1,j = col + 1; i >= 0 && j < n;i --,j ++) { // 左上
            if (board[i][j] == 'Q')
            return false;
        }
        for (int i = row - 1, j = col - 1;i >= 0 && j >= 0; i--, j--) {  // 右上
            if (board[i][j] == 'Q')
            return false;
        }
        return true;
    }
};
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

（3）复杂度分析