回溯算法 典型习题

vector<vector<int>> res;
vector<int> path;void dfs() {if (递归终止条件){res.push_back(path);return;}// 递归方向for (xxx) {path.push_back(val);dfs();path.pop_back();}
}

1.涉及枚举

2.不确定 for 循环的次数

总结

枚举各种可能的情况。

0.直接枚举子集

1.约束条件是子集中数字的和 39

2.约束条件是子集的大小 77 46 47

3.约束条件是1 2两者的结合 2161

4.约束条件是集合数 + sum 93 698

5.去重：同层删去相同的递归起点

6.约束条件是 子集中数的大小关系 491

7.前一个情况可能是后一个情况的约束 51

77

第一层可以选 1 2 3 4

第二层可以选 234 134 ...

需要 path 存储选择的路径。需要 index 作为元素下标。

class Solution {
public:// 储存当前路径vector<int> path;vector<vector<int>> res;vector<vector<int>> combine(int n, int k) {dfs(1, n, k);return res;}void dfs(int index, int n, int k) {// 比如 k = 2, n = 4, index = 4// 不足以构成数组，要提前结束if (path.size() + (n - index + 1) < k) return;// 如果路径的长度是 k，那么把这个路径加入到结果数组if (path.size() == k) {res.push_back(path);return;}// 否则的话，从 index 开始回溯for (int i = index; i <= n; ++i) {path.push_back(i);dfs(i + 1, n, k);path.pop_back();}}
};

39

target = 7

2 2 3/ 2 3 2

3 4

递归树：

s1 2 3 6 7

s2 2367 2367 ...

s3 2367 ...

这一次选了2，下一次从>=2开始选

class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {//先排序sort(candidates.begin(), candidates.end());// 从index = 0的位置开始选，一开始 sum = 0dfs(0, 0, candidates, target);return res;}void dfs(int index, int sum, vector<int>& candidates, int target) {if (sum >= target) {if (sum == target) {res.push_back(path);}return;}// 这次选了 index 下次从 index 开始选for (int i = index; i <= candidates.size() - 1; ++i) {if (sum + candidates[i] > target) return;path.push_back(candidates[i]);// 更新 sumdfs(i, sum + candidates[i], candidates, target);path.pop_back();}}
};

40 同层去重

和39的区别是不能重复

# 模板
class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());dfs(0, 0, candidates, target);return res;}void dfs(int index, int sum, vector<int>& candidates, int target) {if (sum >= target) {if (sum == target) {res.push_back(path);}return;}// 循环 + 递归for () {}}
};

class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());dfs(0, 0, candidates, target);return res;}void dfs(int index, int sum, vector<int>& candidates, int target) {if (sum >= target) {if (sum == target) {res.push_back(path);}return;}// 同层去重// 递归起点都是2，那么后面可以不必递归了unordered_set<int> occ;for (int i = index; i <= candidates.size() - 1; ++i) {if (occ.find(candidates[i]) != occ.end()) {continue;}occ.insert(candidates[i]);path.push_back(candidates[i]);dfs(i + 1, sum + candidates[i], candidates, target);path.pop_back();}}
};

216 固定数据集

class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> combinationSum3(int k, int n) {dfs(1, 0, k, n);return res;}void dfs(int index, int sum, int k, int n) {if (sum >= n) {// 选 k 个数 和为 nif (sum == n && path.size() == k) {res.push_back(path);}}for (int i = index; i <= 9; ++i) {if (sum + i > n) {return;}path.push_back(i);dfs(i + 1, sum + i, k, n);path.pop_back();}}
};

93 复原ip地址

遍历字符串长度

根据不同的长度截取子串

class Solution {
public:vector<string> res;vector<string> segMent;vector<string> restoreIpAddresses(string s) {segMent.resize(4);dfs(0, 0, segMent, s);return res;}bool check(string s) {// 要么是 0 要不是 0 开头的// 字符串转数字return (s[0] != '0' || s == "0") && stoi(s) < 256;}string toString(vector<string> &segMent) {string res;for (int i = 0; i < 3; ++i) {res += segMent[i];res += '.';}res += segMent[3];return res;}// void dfs(int index, int segId, vector<string> &segMent, string s){if (index == s.size() || segId == 4) {if (index == s.size() && segId == 4) {res.push_back(toString(segMent));}return;}for (int i = 1; i <= 3; ++i) {if (index +i > s.size()) return;string sub;// 从 index 开始截取长度为 isub = s.substr(index, i);if (check(sub)) {segMent[segId] = sub;dfs(index + i, segId + 1, segMent, s);}}}
};

78 子集

123

path 初始为空

1 2 3

23 3 /

3/  / 

某 index 数取完就从 index + 1 开始取

class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> subsets(vector<int>& nums) {dfs(0, nums);return res;}void dfs(int index, vector<int>& nums) {res.push_back(path);for (int i = index; i <= nums.size() - 1; ++i) {path.push_back(nums[i]);dfs(i + 1, nums);path.pop_back();}}
};

491 非递增子序列

class Solution {
public:vector<vector<int>> res;vector<int> path;vector<vector<int>> findSubsequences(vector<int>& nums) {dfs(0, nums);return res;}unordered_set<int> appear;void dfs(int index, vector<int>& nums) {if (path.size() >= 2) {res.push_back(path);}// 同层去重 [4, 6, 6, 7]unordered_set<int> occ;for (int i = index; i <= nums.size() - 1; ++i) {// 确保当前的递归起点没被遍历过if (occ.find(nums[i]) != occ.end()) continue;occ.insert(nums[i]);// 确保序列一直保持递增if (path.size() > 0 && nums[i] < path.back()) continue;path.push_back(nums[i]);dfs(i + 1, nums);path.pop_back();}}
};

46 全排列

每一次都是从头到尾遍历

class Solution {
public:vector<int> path;vector<int> used;  // 将 vector<bool> 改为 vector<int>vector<vector<int>> res;vector<vector<int>> permute(vector<int>& nums) {used.resize(nums.size(), 0);  // 初始化 used 向量dfs(nums);return res;}void dfs(vector<int>& nums) {if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); ++i) {// 如果数字没被用过则改为被用过，且更新pathif (!used[i]) {used[i] = 1;  // 将 false 改为 1，表示已使用path.push_back(nums[i]);dfs(nums);path.pop_back();used[i] = 0;  // 将 true 改为 0，表示未使用}}}
};

47 不重复全排列

和 46 不同的一点是，

[1,1,2] 会出现 [2,1,1] 两次，那么加一个hash去重

class Solution {
public:vector<vector<int>> res;vector<int> used;vector<int> path;vector<vector<int>> permuteUnique(vector<int>& nums) {used.resize(nums.size(), 0);dfs(nums);return res;}void dfs(vector<int>& nums) {if (path.size() == nums.size()) {res.push_back(path);return;}// 同层去重，去除递归起点相同的同层元素unordered_set<int> occ;for (int i = 0; i < nums.size() ; ++i) {if (!used[i] && (occ.find(nums[i]) == occ.end())) {used[i] = 1;  // 将 false 改为 1，表示已使用path.push_back(nums[i]);dfs(nums);path.pop_back();used[i] = 0;  // 将 true 改为 0，表示未使用}}}
};

698 k 个等和子集

class Solution {
public:vector<int> subs;int ave;bool canPartitionKSubsets(vector<int>& nums, int k) {int sum = 0;// 桶subs.resize(k,0);// 求和sum = accumulate(nums.begin(), nums.end(), 0);// 是否能被 k 整除if (sum % k != 0) {return false;}ave = sum / k;// 先装大的//sort(nums.begin(), nums.end(), greater());sort(nums.begin(), nums.end(), greater());// 从 0 号位置开始return dfs(0, nums, k);}bool dfs(int index, vector<int>& nums, int k) {// 如果已经遍历完了所有数字// 查看每个子集大小if (index == nums.size()) {for (auto sub : subs) {if (sub != ave) {return false;}}return true;}// 对于同一个元素不要尝试和相同的子集unordered_set<int> occ;// 核心逻辑// 分 k 个桶，依次遍历，更新每个桶中元素的值，再 dfs// dfs 时依次选取不同的数字// 如果当前的桶再装入一个数字超过 ave// 去重for (int i = 0; i < k; ++i) {if (subs[i] +  nums[index] > ave || occ.find(subs[i]) != occ.end()) continue;occ.insert(subs[i]);subs[i] += nums[index];if (dfs(index + 1, nums, k)) return true;subs[i] -= nums[index];}return false;}
};

51 皇后

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<bool> col(n, false);vector<bool> diag1(20, false);vector<bool> diag2(20, false);vector<int> queens(n, 0);dfs(0, col, diag1, diag2, queens, n);return res; // 返回结果集}private:vector<vector<string>> res; // 存储结果集// 深度优先搜索函数void dfs(int index, vector<bool>& col, vector<bool>& diag1, vector<bool>& diag2, vector<int>& queens, int n) {if (index == n) {res.push_back(generate(queens, n));return;}for (int i = 0; i < n; ++i) {if (col[i] || diag1[index + i] || diag2[index - i + 9]) continue;queens[index] = i;// 当前行第 i 列放置皇后col[i] = diag1[index + i] = diag2[index - i + 9] = true;dfs(index + 1, col, diag1, diag2, queens, n);col[i] = diag1[index + i] = diag2[index - i + 9] = false;}}// 生成棋盘vector<string> generate(vector<int>& queens, int n) {vector<string> board;for (int i = 0; i < n; ++i) {string row(n, '.');row[queens[i]] = 'Q';board.push_back(row);}return board; // 返回生成的棋盘}
};

汇编

链接

静态