TUNIVERSE

回溯

算法
字数统计: 4.1k阅读时长: 19 min
2024/03/18

回溯算法

组合

[77] 组合

LeetCode Medium

题目

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

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

代码

基础版本代码

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

但是以上方法不够高效，当循环到当前数目且后面所有元素的总个数也不够k的时候，就可以进行剪枝。目前已经选择了的个数是 path.size()，那么还需要 k - path.size() 个元素。假设起始位置为x，终止为n，可得：

1
2
3
n - x + 1 >= k - path.size()
x <= n + 1 - k + path.size()
即 i <= n + 1 - k + path.size()

因此最后的代码为

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

[39] 组合总和

LeetCode Medium

题目

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

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

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

代码

重点：无重复元素但是元素可以被无限选取，但是问的是组合数，所以要进行去重，同时每次回溯的i不变。

先进行排序，然后在for循环里判断当前元素是否和上一个一样，如果一样则说明重复了，则可以直接跳过本层循环。

同时可以进行剪枝，因为排序过了，如果加上当前元素已经超过了target则说明没必要继续搜索，直接break即可。

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:
  vector<int> path;
  vector<vector<int>> ans;
  void backtracking(vector<int>& candidates, int target, int idx) {
    if (target == 0) {
      ans.push_back(path);
      return;
    }
    for (int i = idx; i < candidates.size(); i++) {
      if (target - candidates[i] < 0) break;
      if (i > idx && candidates[i] == candidates[i - 1])
        continue;
      path.push_back(candidates[i]);
      backtracking(candidates, target - candidates[i], i);
      path.pop_back();
    }
  }
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    backtracking(candidates, target, 0);
    return ans;
  }
};

[40] 组合总和Ⅱ

LeetCode Medium

题目

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

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

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

代码

和上一题差不多，有重复元素和没重复元素但是可以无限次选择没什么区别，都是先排序然后判断和上一个元素是否相同，只不过这题idx在回溯里需要加1.

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 {
public:
  vector<int> path;
  vector<vector<int>> ans;
  void backtracking(vector<int>& candidates, int target, int idx) {
    if (!target) {
      ans.push_back(path);
      return;
    }
    for (int i = idx; i < candidates.size() && target - candidates[i] >= 0; i++) {
      if (i > idx && candidates[i] == candidates[i - 1])
        continue;
      path.push_back(candidates[i]);
      backtracking(candidates, target - candidates[i], i + 1);
      path.pop_back();
    }
  }
  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    backtracking(candidates, target, 0);
    return ans;
  }
};

[216] 组合总和Ⅲ

LeetCode Medium

题目

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

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

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

代码

是70组合和39组合总和的叠加版本，限制了元素的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
  vector<int> path;
  vector<vector<int>> ans;
  void backtracking(int k, int n, int idx) {
    if (path.size() == k && n == 0) {
      ans.push_back(path);
      return;
    }
    for (int i = idx; i <= 10 - k + path.size(); i++) {
      if (n - i < 0)  break;
      path.push_back(i);
      backtracking(k, n - i, i + 1);
      path.pop_back();
    }
  }
  vector<vector<int>> combinationSum3(int k, int n) {
    backtracking(k, n, 1);
    return ans;
  }
};

分割

[131] 分割回文串

LeetCode Medium

题目

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

代码

假设当前的初始位置为idx，用for循环遍历到 s.size() - 1 每个位置 s[idx: i] 当前子串是不是回文，如果是回文则进行一次切割加入res，并从下一个位置开始继续纵向搜索，如此递归。

而如果当前位置 i 和起始位置 idx 组成的子串不是回文，则要继续通过for循环横向寻找下一个满足的位置 i。如果本次循环都不满足则根本不会到 idx >= s.size()，循环会在最后的 i < s.size() 直接退出并返回上一层，而上一层做的是将之前切割的部分子串 pop_back() 出去。

也就是只有前面所有切割位置都是回文，才会纵向往下达到 idx >= s.size() 的递归边界条件。

这里的判断回文子串可以直接用一个二维的dp数组一次完成，后续只需要根据 idx 和 i 的值查询保存的dp数组即可。

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
class Solution {
public:
  vector<string> res;
  vector<vector<string>> ans;
  vector<vector<bool>> dp;
  void isPalindrome(string& s) {
    // dp[i][j] = dp[i+1][j-1] && s[i] == d[j]
    int n = s.size();
    dp.resize(n, vector<bool>(n, false));
    for (int i = n - 1; i >= 0; i--) {
      for (int j = i; j < n; j++) {
        if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]))
          dp[i][j] = true;
      }
    }
  }
  void backtracking(string& s, int idx) {
    if (idx >= s.size()) {
      ans.push_back(res);
      return;
    }
    for (int i = idx; i < s.size(); i++) {
      if (!dp[idx][i])  continue;
      string str = s.substr(idx, i - idx + 1);
      res.push_back(str);
      backtracking(s, i + 1);
      res.pop_back();
    }
  }
  vector<vector<string>> partition(string s) {
    isPalindrome(s);
    backtracking(s, 0);
    return ans;
  }
};

[93] 复原IP地址

LeetCode Medium

题目

有效 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 地址。

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

代码

开一个变量用来计算目前已经加入的结果的数量，如果到达了3最后一段另外处理，这样有两个好处：

  • 不用特判处理中间的 . 符号；
  • 可以大量剪枝，前面加入了三段后最后一段可以直接特判不再进行切分，省掉很多时间。

另一个剪枝点是每一个for循环最多只需要往后判断三位，超过三位肯定不满足

isValid() 函数里需要判断的所有情况如下：

  • start > end：是因为可能出现三段把字符串都分完，最后start为s.size()，但是end是固定的s.size() - 1
  • end - start > 2：长度超过三肯定不满足
  • s[start] == '0' && start != end：不为0但是以0开头
  • 以上通过后计算结果值是否小于255即可

因为判断是否满足条件时只需要用到一些简单的条件而不用对字符串进行实际的切分，所以可以等真的满足条件valid之后再进行切分，省掉时间，即不要提早切分。

这题总体的格式和上题目一样，只是在for循环深度backtracking前加入了一个if判断语句。

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:
  string res = "";
  vector<string> ans;
  void backtracking(string& s, int idx, int cnt) {
    if (cnt == 3) {
      if (isValid(s, idx, s.size() - 1)) {
        ans.push_back(res + s.substr(idx, s.size() - idx));
        return;
      }
    }
    for (int i = idx; i < idx + 3 && i < s.size(); i++) { // 最多只需往后验证三位
      if (isValid(s, idx, i)) {
        string str = s.substr(idx, i - idx + 1) + ".", tmp = res;
        res += str;
        backtracking(s, i + 1, cnt + 1);
        res = tmp;
      }
    }
  }
  bool isValid(string& s, int start, int end) {
    if (start > end || end - start > 2)  return false;
    if (s[start] == '0' && start != end)  return false;
    int num = 0;
    for (int i = start; i <= end; i++)
      num = (s[i] - '0') + num * 10;
    if (num > 255) return false;
    else  return true;
  }
  vector<string> restoreIpAddresses(string s) {
    backtracking(s, 0, 0);
    return ans;
  }
};

子集

[78] 子集

LeetCode Medium

题目

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

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

代码

和组合类型差不多，只不过需要每次递归都添加一次res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
  vector<int> res;
  vector<vector<int>> ans;
  void backtracking(vector<int>& nums, int idx) {
    ans.push_back(res);
    if (idx >= nums.size()) return;
    for (int i = idx; i < nums.size(); i++) {
      res.push_back(nums[i]);
      backtracking(nums, i + 1);
      res.pop_back();
    }
  }
  vector<vector<int>> subsets(vector<int>& nums) {
    backtracking(nums, 0);
    return ans;
  }
};

[90] 子集Ⅱ

LeetCode Medium

题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

代码

经典有重复元素排序+去重，核心代码

1
2
3
sort(nums.begin(), nums.end());

if (i > idx && nums[i] == nums[i - 1])  continue;

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
  vector<int> res;
  vector<vector<int>> ans;
  void backtracking(vector<int>& nums, int idx) {
    ans.push_back(res);
    if (idx >= nums.size()) return;
    for (int i = idx; i < nums.size(); i++) {
      if (i > idx && nums[i] == nums[i - 1])  continue;
      res.push_back(nums[i]);
      backtracking(nums, i + 1);
      res.pop_back();
    }
  }
  vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    backtracking(nums, 0);
    return ans;
  }
};

排列

[46] 全排列

LeetCode Medium

题目

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

代码

因为是排列所以不需要idx了，每次从0开始遍历，但是需要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
class Solution {
public:
  vector<int> res, used;
  vector<vector<int>> ans;
  void backtracking(vector<int>& nums, int n) {
    if (res.size() == n) {
      ans.push_back(res);
      return;
    }
    for (int i = 0; i < n; i++) {
      if (used[i])  continue;
      res.push_back(nums[i]);
      used[i] = 1;
      backtracking(nums, n);
      res.pop_back();
      used[i] = 0;
    }
  }
  vector<vector<int>> permute(vector<int>& nums) {
    int n = nums.size();
    used.resize(n, 0);
    backtracking(nums, n);
    return ans;
  }
};

[47] 全排列Ⅱ

LeetCode Medium

题目

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

代码

有重复的元素因此要去重，仍然是排序加上判断相邻节点状态。

以下内容来自代码随想录

去重最为关键的代码为：

1
2
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
  continue;

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

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

如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。

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

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

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

47.全排列II2

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

47.全排列II3

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

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<int> res, used;
  vector<vector<int>> ans;
  void backtracking(vector<int>& nums, int n) {
    if (res.size() == n) {
      ans.push_back(res);
      return;
    }
    for (int i = 0; i < n; i++) {
      if (used[i])  continue;
      if (i > 0 && !used[i - 1] && nums[i] == nums[i - 1]) 
      	continue;
      res.push_back(nums[i]);
      used[i] = 1;
      backtracking(nums, n);
      res.pop_back();
      used[i] = 0;
    }
  }
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    int n = nums.size();
    used.resize(n, 0);
    sort(nums.begin(), nums.end());
    backtracking(nums, n);
    return ans;
  }
};

棋盘

[51] N皇后

LeetCode Hard

题目

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

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

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

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

代码

重点在于检查同一列和和检查斜对角线，见注释。

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
class Solution {
public:
  vector<string> res;
  vector<vector<string>> ans;
  bool isValid(int row, int col, int n) {
    // 不用检查同一行，因为每次放置完都回溯，同一行不可能有多个皇后
    // 同一列上不能有皇后，检查列，查找上面的行
    for (int i = row - 1; i >= 0; i--)
      if (res[i][col] == 'Q') return false;
    // 检查右上的斜对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
      if (res[i][j] == 'Q') return false;
    // 检查左上角的斜对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
      if (res[i][j] == 'Q') return false;
    return true;
  }
  void backtracking(int row, int n) {
    if (row == n) {
      ans.push_back(res);
      return;
    }
    for (int col = 0; col < n; col++) {
      if (isValid(row, col, n)) {
        res[row][col] = 'Q';
        backtracking(row + 1, n);
        res[row][col] = '.';  // 回溯
      }
    }
  }
  vector<vector<string>> solveNQueens(int n) {
    res.resize(n, string(n, '.'));
    backtracking(0, n);
    return ans;
  }
};

[37] 解数独

LeetCode Hard

题目

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

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

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

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

代码

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 {
public:
  bool isValid(int row, int col, vector<vector<char>>& board, char k) {
    // 检查同一行有没有相同的
    for (int i = 0; i < 9; i++)
      if (board[row][i] == k) return false;
    // 检查同一列有没有相同的
    for (int i = 8; i >= 0; i--)
      if (board[i][col] == k) return false;
    // 检查九宫格
    int r = (row / 3) * 3, c = (col / 3) * 3;
    for (int i = r; i < r + 3; i++)
      for (int j = c; j < c + 3; j++)
        if (board[i][j] == k) return false;
    return true;
  }
  bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {
      for (int j = 0; j < board[0].size(); j++) {
        if (board[i][j] == '.') {
          for (char k = '1'; k <= '9'; k++) {
            if (isValid(i, j, board, k)) {
              board[i][j] = k;
              if (backtracking(board))
                return true;  // 如果找到成功的立刻返回
              // 没找到失败了，撤销一下刚才的填写
              board[i][j] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }
  void solveSudoku(vector<vector<char>>& board) {
    backtracking(board);
  }
};
CATALOG
  1. 1. 组合
    1. 1.1. [77] 组合
      1. 1.1.1. 题目
      2. 1.1.2. 代码
    2. 1.2. [39] 组合总和
      1. 1.2.1. 题目
      2. 1.2.2. 代码
    3. 1.3. [40] 组合总和Ⅱ
      1. 1.3.1. 题目
      2. 1.3.2. 代码
    4. 1.4. [216] 组合总和Ⅲ
      1. 1.4.1. 题目
      2. 1.4.2. 代码
  2. 2. 分割
    1. 2.1. [131] 分割回文串
      1. 2.1.1. 题目
      2. 2.1.2. 代码
    2. 2.2. [93] 复原IP地址
      1. 2.2.1. 题目
      2. 2.2.2. 代码
  3. 3. 子集
    1. 3.1. [78] 子集
      1. 3.1.1. 题目
      2. 3.1.2. 代码
    2. 3.2. [90] 子集Ⅱ
      1. 3.2.1. 题目
      2. 3.2.2. 代码
  4. 4. 排列
    1. 4.1. [46] 全排列
      1. 4.1.1. 题目
      2. 4.1.2. 代码
    2. 4.2. [47] 全排列Ⅱ
      1. 4.2.1. 题目
      2. 4.2.2. 代码
  5. 5. 棋盘
    1. 5.1. [51] N皇后
      1. 5.1.1. 题目
      2. 5.1.2. 代码
    2. 5.2. [37] 解数独
      1. 5.2.1. 题目
      2. 5.2.2. 代码
Total : 65
2024
2023
2022
2021
2020
动态规划 计算机视觉 三维重建 深度学习 查找 教程 MongoDB 数据库 Neo4j MySQL 机器学习 GNN 随笔 托福 故障诊断 Greenplum操作 Linux磁盘扩容 debug记录 环境问题 多维索引 磁盘故障 迁移学习 列存分区 链表 LeetCode 双指针 剪枝 素数 逻辑题 并查集 树的遍历 哈希 字符串 排序 二叉搜索树 数学模拟 图论 完全二叉树 最短路径 贪心 Set AVL树 图模拟 DFS 快乐模拟 拓扑排序 栈 图的遍历 递推 前端 React Webpack Eslint top
算法 华科课程 学习笔记 英语 年末总结 腾讯AI训练营