77. 组合
暴力回溯
组合问题，经典的回溯问题
可以看出这个棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现n相当于树的宽度，k相当于树的深度。
那么如何在这个树上遍历，然后收集到我们要的结果集呢？
图中每次搜索到了叶子节点，我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
套用回溯的模板
参数为n，k，和startIndex（记录下一层递归的起始位置）
vector<vector<int>> result; // 存放符合条件结果的集合vector<int> path; // 用来存放符合条件单一结果void backtracking(int n, int k, int startIndex)
终止条件
path数组的大小如果达到了k，那么就找到了符合条件的一个组合（到了叶子结点），这时候需要返回
如红色部分：
这时候需要将path保存到result，结束本次循环
if (path.size() == k) {result.push_back(path);return;}
- 单层搜索的过程
回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历path.push_back(i); // 处理节点backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始path.pop_back(); // 回溯，撤销处理的节点}
举个栗子：n = 4, k = 2
第一层递归：startIndex的范围 [1, 2, 3, 4] ，表示从1，2，3，4中挑一个（横向）
第二层递归：startIndex的范围 [2, 3, 4]，表示从2，3，4中挑一个（横向）
第三层递归：path.size() == 2 了，那么保存结果
完整代码：
class Solution {public:vector<vector<int>> result; // 保存要返回的结果vector<int> path; // 保存每一个组合// 回溯法void backtracking(int n, int k, int startIndex) {if (path.size() == k) { // 满足条件，保存结果result.push_back(path);return;}// 搜索for (int i = startIndex; i <= n; i++) {path.push_back(i);backtracking(n, k, i + 1);path.pop_back(); // 回溯}}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}};
剪枝优化
可以剪枝的地方在递归中每一层的for循环所选择的起始位置。
一共n个元素，组成k个元素的组合还需要 k - path.size() 个，当剩余元素数量不足时，可以直接跳过，因此每一层的起始位置不能超过n - (k - path.size()) + 1
优化后代码：
class Solution {public:vector<vector<int>> result; // 保存要返回的结果vector<int> path; // 保存每一个组合// 回溯法void backtracking(int n, int k, int startIndex) {if (path.size() == k) { // 满足条件，保存结果result.push_back(path);return;}// 搜索for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {path.push_back(i);backtracking(n, k, i + 1);path.pop_back(); // 回溯}}vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}};
216. 组合总和 III
有了第77题的经验，这道题写起来就快多了
回溯
咔咔一顿写
i的范围（横向遍历）为1-9
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(int k, int n, int start, int sum) {
if (path.size() == k) {
if (sum == n) {
res.push_back(path);
}
return;
}
// 如果 sum + i 超过n，直接break
for (int i = start; i <= 9 && sum + i <= n; ++i) {
path.push_back(i);
dfs(k, n, i + 1, sum + i);
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, 1, 0);
return res;
}
};
17. 电话号码的字母组合
回溯
读题后，先看一下字符串是如何组合的，看一下使用回溯横向和纵向的过程
了解了组合的过程，就大致有了解题思路
准备工作
vector
string path 来记录组合
unorder_map
class Solution {
public:
vector<string> result;
string path;
unordered_map<char, string> ht{
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
void backtracking(string& digits, int index) {
if (index == digits.size()) {
result.push_back(path);
return;
}
for (auto c : ht[digits[index]]) {
path.push_back(c);
backtracking(digits, index + 1);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
result.clear();
if (digits.empty()) return result; // 如果digit为空，直接返回
backtracking(digits, 0);
return result;
}
};
备注：题目中测试样例没有 1，# 等异常输入，因此没有考虑，在实际中应该考虑这些特殊情况
39. 组合总和
这个和电话号码的字母组合有点像，电话号码哪道题，每次横向遍历，处理的是数字对字母的映射，这道题横向遍历candidates就好了，
组合的和达到要求后，可以进行剪枝操作
理解一下candidates中数字可以无限制取的意思：一个数字可以取多次
但它毕竟是组合，返回的结果中保证path（一种组合）是唯一的（[2,2,3]和[2, 3, 2]）是一样的，因此再for循环中，要满足同一个元素可以重复取，又要保证每个path唯一，就需要一个startIndex来作为递归的参数
比如第一层选2，第二，第三层还能选2，但是第一层选3，以后的层不能选2了，因为3,2和2,3是重复的
完整代码：
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& candidates, int target, int start) {
if (target < 0)
return;
if (target == 0) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size(); ++i) {
path.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i); // 一个数字可以重复取，因此从i开始
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, target, 0);
return res;
}
};
剪枝
剪枝的for循环
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& candidates, int target, int start) {
if (target < 0)
return;
if (target == 0) {
res.push_back(path);
return;
}
// 加上 target - candidates[i] >= 0 这个剪枝条件需要保证candidates有序
for (int i = start; i < candidates.size() && target - candidates[i] >= 0; ++i) {
path.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i); // 一个数字可以重复取，因此从i开始
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0);
return res;
}
};
因为需要一个O(nlogn)复杂度的快速排序，所以剪枝是否真的能够提高效率还不好说
40. 组合总和 II
这道题限定每个元素只能用一次，但是有重复元素，要修改39题中单层搜索的逻辑，使用i+1
但问题在于candidates中含有重复元素，并且结果中不能有重复的组合，所以要在搜索的过程中去重（先对数组去重可能超时）
一个组合中可以有重复，但是相同的组合只能出现一次，可以用一个数组，记录该位置的元素是否使用过
回溯三部曲：
- 参数：
在39题的基础上，在加一个used用于记录树枝上的元素是否使用过
终止条件
if (sum > target) { // 这个条件其实可以省略 return; } if (sum == target) { result.push_back(path); return; }单层搜索的逻辑
这道题要考虑如何去重，这是重点
元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！
Note：
得到组合的的顺序从树的角度来看，是从根到叶子节点的不断选取，这整个路径就是一个组合，第i层选择的是组合第i个位置。一个组合中可以有相同的元素，也就是说：如果candidates中有两个1的话，第一层，选1，下一层可以选1；如果从树的某一层的角度来看的话，这个位置选1后，相同层再选1的话，相当于在这个位置用了两次一，那么从这两根树继续dfs下去，得到的结果必然是重复的
如果不排序要去重的话就得用哈希表了。
要去重的是“同一树层上的使用过”，如果判断同一树层上元素（相同的元素）是否使用过了呢。
如果**candidates[i] == candidates[i - 1]** 并且** used[i - 1] == false**，就说明：前一个树枝，使用了**candidates[i - 1]**，也就是说同一树层使用过**candidates[i - 1]**。
此时for循环里就应该做continue的操作。
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// used[i - 1] == true，说明同一树支candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, i + 1, used); // 和39.组合总和的区别1：这里是i+1，每个数字在每个组合中只能使用一次
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
完整代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum = 0;
void backtracking(vector<int>& candidates, int target, int startIndex, vector<bool>& used) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// used[i - 1] == true，说明同一树支candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(), false);
path.clear();
result.clear();
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, used);
return result;
}
};
其实不用used，直接用startIndex来去重也是可以的
首先我们要知道candidates这个数组是固定的，其次candidates[i]==candidate[i-1]这个条件控制的是仅仅是前后元素是否相等，但是单纯用这一条件的话会导致同一跟树枝（纵向）出现相同元素也会被剪掉，就是连[1, 1, 6]这种答案都不可以出现。但是一旦加了 i > startIndex 这个条件就不一样了，因为如果在同一根树枝上进行迭代 i一直是等于 startIndex 的，只有横向的时候才会出现 i > startIndex的情况，所以 i > startIndex && candidates[i]==candidate[i-1]可以进行树层去重.
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum = 0;
void backtracking(vector<int>& candidates, int target, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// 要对同一树层使用过的元素进行跳过
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, i + 1); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(), false);
path.clear();
result.clear();
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0);
return result;
}
};
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& candidates, int target, int start, vector<bool>& used) {
if (target < 0) {
return;
}
if (target == 0) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size() && target - candidates[i] >= 0; ++i) {
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) { // 这一层用过这个数字了
continue;
}
path.push_back(candidates[i]);
used[i] = true;
dfs(candidates, target - candidates[i], i + 1, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<bool> used(candidates.size(), false);
dfs(candidates, target, 0, used);
return res;
}
};
不用used
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& candidates, int target, int start) {
if (target < 0) {
return;
}
if (target == 0) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size() && target - candidates[i] >= 0; ++i) {
if (i > start && candidates[i] == candidates[i - 1]) continue; // 这一层用过这个数字了
path.push_back(candidates[i]);
dfs(candidates, target - candidates[i], i + 1);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0);
return res;
}
};
22. 括号生成
class Solution {
public:
vector<string> res;
string path;
void dfs(int n, int l, int r, int start) {
if (l == n && r == n) {
res.push_back(path);
return;
}
for (int i = start; i < 2 * n; i++) {
if (l < n) { // 可以放左括号
path.push_back('(');
dfs(n, l + 1, r, i + 1);
path.pop_back();
}
if (r < l) {
path.push_back(')');
dfs(n, l, r + 1, i + 1);
path.pop_back();
}
}
}
vector<string> generateParenthesis(int n) {
dfs(n, 0, 0, 0);
return res;
}
};
若有收获，就点个赞吧
0 人点赞
