摘要
- 回溯法的答案去重可分为两种，将回溯法的搜索过程抽象成树形，在树的同一层需要去重（去掉重复的组合可能，称为树层去重），在树的同一条路径上需要去重（去掉重复选择的元素，称为树枝去重）。
- 分割回文子串，首先要定义好如何进行分割，方便构造出树形结构来用回溯法搜索答案。
LeetCode39 组合总和
-
按照回溯法的三步进行思考：
-
递归的终止条件：当前组合中元素的和等于
target，收集结果后返回；剪枝条件：当前组合中元素的和大于target，直接返回。 - 递归函数需要的参数随分析问题的过程确定
- 单层递归的处理逻辑：枚举还没有被尝试过的元素，选择一个元素加入组合，然后再下一层中，也从当前元素开始尝试加入组合（因为可以无限制地重复选取一个元素）。
-
递归的终止条件：当前组合中元素的和等于
-
这道题与 组合总和III （216. 组合总和 III - 力扣（Leetcode））的区别：
- 组合总和III 通过
start控制当前节点向下一层搜索时，能从1-9中选择的元素的起始下标，这可以防止重复选择在上一层已经选择过的元素。 - 这道题可以重复选择元素，所以下一层的
start应该保留当前的i。
- 组合总和III 通过
完整的题解代码如下
class Solution {
public:
void backtracking(vector<int>& candidates, int target, vector<vector<int>>& res,
vector<int>& cur, int sum, int start)
{
if (sum > target) return;
if (sum == target) {
res.push_back(cur);
return;
}
for (int i = start; i < candidates.size(); i++) {
cur.push_back(candidates[i]);
sum += cur.back();
backtracking(candidates, target, res, cur, sum, i);
sum -= cur.back();
cur.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> cur;
backtracking(candidates, target, res, cur, 0, 0);
return res;
}
};
LeetCode40 组合总和II
- 初步尝试写了代码，观察测试用例的输入和输出，发现结果中出现了重复的组合
[图片上传失败...(image-f0251d-1682956080332)]
-
这提醒我这道题需要进行去重，在这道题中，去重可以应分为两种：
- 一是不要重复选取同一个元素，题目要求
candidates每个数字在每个组合中只能使用一次。另外，这道题目中元素的值可以相同，不同的元素可以有相同的值。 - 二是结果中不能出现相同的组合，组合不强调元素的顺序，如
[1,2,5]和[2,1,5]是相同的组合，它们中只有一个能出现在正确答案中。
- 一是不要重复选取同一个元素，题目要求
先将搜索过程抽象为树形结构，以
candidates = [1,1,2], target = 3为例
- 先看
[]->[1]->[1, 1]->[1, 1, 2]这条路径，在这条“树枝”上的组合中出现了两个1，这是合理的，因为candidates中本来就有两个1，我们选取的是不同的元素。“树枝去重”的关键是控制从本层递归中从哪里开始选取元素，不要重复选取相同的元素（即在candidates中的下标相同）。所以下一层递归应该从当前元素的下一个元素开始选取。 - 再看
[]->[1]->[1, 2]这条路径，这条路径出现了两次，使得[1, 2]这个组合出现了两次。这个重复并不是选取相同的元素造成的，而是选择了值相同的不同元素造成的重复。在树的第二层中选取第一个1开始搜索，再向下搜索到的组合，已经包含了在第二层中选取第二个1的所有情况，所以造成了重复。这是在树的同一层中因为选取值相同的不同元素造成的重复，所以对应的去重叫做“树层去重”。 - 对
candidates进行排列，可以让值相同的元素相邻，让值相同的元素连续分布在candidates中，这样就方便我们辨别：在树的同一层中，是否以值相同的元素继续向下搜索。在树的同一层中，第一次选取到1（或者某个值），第一次再向下搜索的情况就已经包含了第二次、第三次……再以1继续向下搜索的情况。所以，只保留在树的同一层中，第一次选取到当前值的情况，就可以完成“树层去重”。
完整的题解代码如下
class Solution {
public:
void backtracking(vector<int>& candidates, int target, vector<vector<int>>& res,
vector<int>& cur, int sum, int start)
{
if (sum > target) return;
if (sum == target) {
res.push_back(cur);
return;
}
for (int i = start; i < candidates.size(); i++) {
if (i - start && candidates[i - 1] == candidates[i]) continue;
cur.push_back(candidates[i]);
sum += cur.back();
backtracking(candidates, target, res, cur, sum, i + 1);
sum -= cur.back();
cur.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> cur;
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, res, cur, 0, 0);
return res;
}
};
- 通过
i - start是否为0，可以区分candidates[i - 1] == candidates[i]的值是在树的同一层重复了还是在同一条路径上重复了。直观地理解是这样：每层的i都从start开始，既然i == start时是在本层中第一次选取元素，自然不是在同一层中两次选取值相同的不同元素的情况（i == start时是在本层中第一次选取元素，才选取了一次，当然不会两次选取到相同值）。
LeetCode131 分割回文串
- 分割回文串，首先要定义如何“分割”。分割采用左闭右闭区间，从左到右逐个子串进行分割。以
"aab"为例：
-
|作为分割符，采用左闭右闭区间进行分割。参照上述例子，来分析回溯法的递归函数如何实现：- 递归的终止条件：分割完整个字符串，即分隔符已经到字符串末尾。在剪枝条件中，若出现非回文子串，则直接剪枝，保证最终收集的答案中的子串都是回文串。
- 递归函数需要的参数：当前层分割符可用的开始位置。
- 单层递归的逻辑：从左到右枚举当前层的分割可能，枚举一种可能时，判断新分割出的子串是否是回文串。如果当前分割出的子串不是回文串，则可以剪枝，不需要再向下搜索。
完整的题解代码如下
class Solution {
public:
bool isPalindrome(const string& s, int l, int r) {
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}
void backtracking(const string& s, vector<vector<string>>& res,
int start, vector<string>& cur)
{
if (start == s.size()) {
res.push_back(cur);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) {
cur.push_back(s.substr(start, i - start + 1));
backtracking(s, res, i + 1, cur);
cur.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> cur;
backtracking(s, res, 0, cur);
return res;
}
};
