代码随想录训练营第27天|LeetCode 39. 组合总和、40.组合总和II、 131.分割回文串

参考

代码随想录

题目一：LeetCode 39.组合总和

依旧是组合问题，只是稍有不同：第一点是集合元素通过数组给出，第二点是元素可以重复，第三点是不限制每个组合的元素个数。针对第一点，用原来的i指针来得到数组中的元素而不是直接作为元素；第二个点，则递归调用的时候从当前元素开始递归而不是原来的下一个元素；第三个点，终止条件上需要补充，当当前路径的和等于目标和的时候就要返回了，这里不能再用path的大小来判断，而应该用当前路径的和与目标和的关系。

1. 确定递归函数的参数和返回值
   参数：数组candidates，要从中获取元素；目标值target，每次递归要用当前和与目标和作比较，当大于等于时递归结束；每次递归的起始位置start，每次递归不能都从0开始，如果都从0开始，得到的结果中会有重复的数组。

void backtracking(vector<int>& candidates,int target,int start)
1

同样用全局变量path来保存路径，result来保存结果，sum来保存当前路径和。

int sum = 0;
vector<int> path;
vector<vector<int>> result;
1
2
3

2. 确定递归终止条件：这里不限制组合元素的个数，所以不能用path的大小来判断是否结束递归，而应该用sum和target的大小来判断。若sum == target，则说明找到了满足条件的数组，保存这个数组然后就可以结束本此递归了。若target > sum，因为都是正数，所以继续往下找不可能找到满足条件的数组，所以可以直接返回了。

if(sum == target){
    result.push_back(path);
    return;
}
if(sum > target) return;
1
2
3
4
5

3. 确定单层搜索逻辑：用for循环来遍历树形结构的宽度，递归来遍历深度，递归结束后进行回溯。

for (int i = start; i < candidates.size(); i++){
    sum += candidates[i];
    path.push_back(candidates[i]);
    backtracking(candidates,target,i);
    sum -= candidates[i];
    path.pop_back();
}  
1
2
3
4
5
6
7

注意，其中下一个开始遍历指针时当前的i，而不是下一个i+1，因为每个元素是可以重复的。
完整的代码实现如下：

class Solution {
public:
    void backtracking(vector<int>& candidates,int target,int start)
    {
        if(sum == target){
            result.push_back(path);
            return;
        }
        if(sum > target) return;

        for (int i = start; i < candidates.size(); i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,i);
            sum -= candidates[i];
            path.pop_back();
        }  
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0);
        return result;
    }
private:
    int sum = 0;
    vector<int> path;
    vector<vector<int>> 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

剪枝优化

如果要进行剪枝优化，需要对数组进行从小到大的排列，如果判断出下一次递归后和大于target了，就不再递归了，直接结束，下一次递归后的和为sum + candidates[i]。注意，如果不剪枝，则不需要排序。加入剪枝的代码如下：

class Solution {
public:
    void backtracking(vector<int>& candidates,int target,int start)
    {
        if(sum == target){
            result.push_back(path);
            return;
        }
        if(sum > target) return;

        for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,i);
            sum -= candidates[i];
            path.pop_back();
        }  
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0);
        return result;
    }
private:
    int sum = 0;
    vector<int> path;
    vector<vector<int>> 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

题目二：LeetCode 40.组合总和II

这个题的难点在于怎么去重，因为给定的数组中有重复的元素，如果按照之前的做法，那求得的结果中必定有重复的数组。
组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成没有彻底理解去重的根本原因。回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

1. 确定递归函数的参数和返回值：
   参数：数组candidates，要从中获取元素；目标值target；每次遍历的起始位置startIndex；用于判断元素是否使用过的used。
   返回值：无

void backtracking(vector<int>& candidates,int target,int startIndex,vector<bool>& used)
1

另外用全局变量来保存遍历路径和最终的结果，sum来保存路径之和。

int sum = 0;
vector<int> path;
vector<vector<int>> result;
1
2
3

2. 确定递归终止条件：当sum > target的时候直接返回；当sum == target时保存结果之后再返回。

if(sum > target)    return;
if(sum == target){
    result.push_back(path);
    return;
}
1
2
3
4
5

3. 确定单层递归逻辑：这里就是这题和之前的题不同的地方了。要保证得到的组合不重复，所以在同一层上不能出现这一层之前使用过的元素。这里用一个数组used来记录某一个元素在这一层上是否被使用过。used数组初始化为false，**如果在遍历深度的时候使用过就将对应的used标记置为true，在回溯的 时候置为false，这样如果used为false，说明这一层上已经被使用过了。**这里的true和false怎么用都可以，只要能判断出在这一层上有没有用过就可以了。

for(int i = startIndex; i < candidates.size(); i++){
            if(i > 0 && candidates[i-1] == candidates[i] && used[i-1] == false) continue;  //去重
            used[i] = true;
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,i+1,used);
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
1
2
3
4
5
6
7
8
9
10

完整的代码实现如下：

class Solution {
public:
    void backtracking(vector<int>& candidates,int target,int startIndex,vector<bool>& used)
    {
        if(sum > target)    return;
        if(sum == target){
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size(); i++){
            if(i > 0 && candidates[i-1] == candidates[i] && used[i-1] == false) continue;  //去重
            used[i] = true;
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,target,i+1,used);
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(),false);
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,used);
        return result;
    }
private:
    int sum = 0;
    vector<int> path;
    vector<vector<int>> 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

注意，需要对给定的数组进行排序。另外，也可以像上一个题一样进行剪枝优化。

题目三：LeetCode 131 分割回文串

和之前的组合一样，还是要用for循环加递归，用for循环遍历树形结构的宽度，递归遍历树形结构的深度，for–>i，递归–>startIndex.

1. 确定递归函数的参数和返回值
   参数：字符串s，递归的起始位置startIndex
   返回值：无
   用path来保存分割的子串，result来保存最终的结果。

vector<string> path;
vector<vector<string>> result;
void backtracking(string& s,int startIndex);
1
2
3

2. 确定递归终止条件：当startIndex == s.size()的时候说明已经分割到末尾了，可以保存分割结果并返回了。

if(startIndex == s.size()){
 	result.push_back(path);
    return;
}
1
2
3
4

3. 确定单层搜索逻辑：在for (int i = startIndex; i < s.size(); i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文，如果是回文，就加入在vector path中，path用来记录切割过的回文子串。

for(int i = startIndex; i < s.size();i++){
	string str = s.substr(startIndex,i-startIndex+1);
   	if(isVaild(str))    path.push_back(str);
   	else continue;
   	backtracking(s,i+1);
   	path.pop_back();
}
1
2
3
4
5
6
7

其中判断是否为回文串用双指针来实现，一个指针从前开始，一个指针从后开始，两个指针向中间移动，代码如下：

bool isVaild(string& str){  //判断是否为回文串
	  int left = 0, right = str.size()-1;
	  while(left < right){
	      if(str[left] != str[right]) return false;
	      left++,right--;
	  }
	  return true;
}
1
2
3
4
5
6
7
8

完整代码如下：

class Solution {
public:
    bool isVaild(string& str){  //判断是否为回文串
        int left = 0, right = str.size()-1;
        while(left < right){
            if(str[left] != str[right]) return false;
            left++,right--;
        }
        return true;
    }
    void backtracking(string& s,int startIndex){
        if(startIndex == s.size()){
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < s.size();i++){
            string str = s.substr(startIndex,i-startIndex+1);
            if(isVaild(str))    path.push_back(str);
            else continue;
            backtracking(s,i+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return result;
    }
private:
    vector<string> path;
    vector<vector<string>> 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