39.组合总和

标题链接：39.组合总和

本题是 调集里元素能够用无数次，那么和组合问题的不同 其实仅在于 startIndex 上的控制

难度指数：

Q：假如调集里边有0，你还重复选取，那不就死循环了吗？

A：不必担心，组合里边的元素都是正整数。

树形结构：

本题用 target 来约束树的高度

代码思路：

界说全局变量：

• 二维数组 vector<vector<int>> result;

• 一维数组vector<int> path;

sum 用来统计 path 里边的和；也能够不必 sum，能够用 target 做相应的减操作，最终假如 target = 0，正好阐明找到了一个组合，和等于 target。

（这儿也能够直接 sum(path) 放进判别句子，实质一样的，也便是少了两行代码而已哈哈哈哈哈）

vector<vector<int>> result;
vector<int> path;
void backtracking(candidates, target, sum, startIndex) {
  if (sum > target) {
    return;
   }
  if (sum == target) {
    result.push_back(path);
    return;
   }
  for (int i = startIndex; i < candidates.size(); i++) {
    sum += candidates[i];
    path.push_back(candidates[i]);
    backtracking(candidates, target, sum, i);
    sum -= candidates[i];
    path.pop_back();
   }
}

AC代码： （中心代码形式）

class Solution {
private:
  vector<vector<int>> result;
  vector<int> path;
  void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
    if (sum > target) {
      return;
     }
    if (sum == target) {
      result.push_back(path);
      return;
     }
    for (int i = startIndex; i < candidates.size(); i++) {
      sum += candidates[i];
      path.push_back(candidates[i]);
      backtracking(candidates, target, sum, i); //递归
      sum -= candidates[i]; //回溯
      path.pop_back();
     }
   }
public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    result.clear();
    path.clear();
    backtracking(candidates, target, 0, 0);
    return result;
   }
};

剪枝（优化）：

在用回溯法处理类似问题的时候，剪枝一般要在这个 for循环 做文章

对总调集排序之后，假如下一层的sum（便是本层的 sum + candidates[i]）现已大于target，就能够完毕本轮for循环的遍历。

树形结构：

AC代码： （中心代码形式）

class Solution {
private:
  vector<vector<int>> result;
  vector<int> path;
  void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
    if (sum == target) {
      result.push_back(path);
      return;
     }
    
    //假如 sum + candidates[i] > target  就停止遍历
    for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
      sum += candidates[i];
      path.push_back(candidates[i]);
      backtracking(candidates, target, sum, i); //递归
      sum -= candidates[i]; //回溯
      path.pop_back();
     }
   }
public:
  vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    result.clear();
    path.clear();
    sort(candidates.begin(), candidates.end()); //需求排序
    backtracking(candidates, target, 0, 0);
    return result;
   }
};

40.组合总和Ⅱ

好题

标题链接：40.组合总和Ⅱ

本题开端涉及到一个问题了：去重。

留意标题中给咱们的调集是有重复元素的，那么求出来的组合有可能重复，但标题要求不能有重复组合。 （需求去重）

难度指数：

你可能会这么想：我就直接用之前的方式进行查找，查找出来若干个组合，这些组合中可能有重复的，然后用 map 或 set 做去重，将去重后的组合输出。

思路没啥问题，但完成起来麻烦，且容易超时。

代码思路：

咱们能够在查找的过程中直接进行去重

（说人话：使用过的元素不再使用，避免重复）要了解这道题的精华。

• 树层去重
• 树枝去重

能够用回溯算法处理的任何问题都能够笼统成一个树形结构。

为了了解去重咱们来举一个比如，candidates = [1, 1, 2], target = 3 ，（便利起见 candidates现已排序了）

想要去重需求先进行排序

对应的这个下标，用过就赋成1，没用过赋成0，能够把它界说成 bool 类型。

树形结构：

去重的关键在 树层去重

一维数组 path ：寄存契合条件的单个组合（途径）

二维数组 result ：寄存各个组合的成果集

这儿递归函数无须回来值，因而函数回来类型是 void ；寄存组合的成果集也都放在全局变量。

Sum 记载单条途径搜集的成果和，startIndex 确保组合中不能重复使用相同的元素,

used[] 数组标记元素是否使用过（使用过标记为true）

考虑：为什么是 used[i - 1] == 0 而不是 used[i - 1] == 1 ？

vector<int> path; //寄存契合条件的单个组合
vector<vector<int>> result; //寄存组合调集
void backtracking(nums, targetSum, Sum, startIndex, used) {
  //停止条件
  if (Sum > targetSum) {
    return;
   }
  if (Sum == targetSum) {
    result.push_back(path); //放进成果集
    return;
   }
  //单层查找的逻辑
  for (int i = startIndex; i < nums.size(); i++) { //取1      取1      取2
    //树层上要进行去重
    if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) { //假如当前遍历元素和前一个元素相同   (i>0是为了防止后边的i-1数组越界)
      continue; //便是说这儿不取1了，持续往后取  (这便是去重)
     }
    path.push_back(nums[i]); //搜集单个组合
    Sum += nums[i];
    used[i] = true;
    backtracking(nums, targetSum, Sum, i + 1, used); //递归
    path.pop_back(); //回溯
    Sum -= nums[i];  //回溯
    used[i] = false; //回溯
   }
}

注：力扣上主函数在调用这个函数之前要先对nums[] 这个调集进行排序。

⚠️去重操作是在排完序之后进行去重的！

AC代码： （中心代码形式）

class Solution {
private:
  vector<int> path; //寄存契合条件的单个组合
  vector<vector<int>> result; //寄存组合调集
  void backtracking(vector<int>& nums, int targetSum, int Sum, int startIndex, vector<bool>& used) {
    //停止条件
    if (Sum > targetSum) {
      return;
     }
    if (Sum == targetSum) {
      result.push_back(path); //放进成果集
      return;
     }
    //单层查找的逻辑
    for (int i = startIndex; i < nums.size(); i++) { //取1 取1 取2
      //树层上要进行去重
      if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) {
        continue;
       }
      path.push_back(nums[i]); //搜集单个组合
      Sum += nums[i];
      used[i] = true;
      backtracking(nums, targetSum, Sum, i + 1, used); //递归
      path.pop_back();
      Sum -= nums[i];
      used[i] = false;
     }
   }
public:
  vector<vector<int>> combinationSum2(vector<int>& nums, int targetSum) {
    int Sum, startIndex;
    vector<bool> used(nums.size(), false);
    path.clear();
    result.clear();
    //先对nums进行排序，让其相同的元素都挨在一起
    sort(nums.begin(), nums.end());
    backtracking(nums, targetSum, 0, 0, used);
    return result;
   }
};

131.切开回文串

切开问题其实是一种组合问题！

标题链接：131.切开回文串

难度指数：

代码思路：

一维数组 path ：寄存契合条件的单个组合（途径）

二维数组 result ：寄存组合调集

这两个全局变量，咱们也是能够考虑放到递归的参数里边。

startIndex 确保切开过的不会重复切开； startIndex 便是切开线（的位置）。

⚠️C++er，留意传入递归函数的参数是const，还是引用之类的。

if (startIndex == s.size()) { //阐明现已到了叶子节点 
    result.push_back(path); 
    return;
}

↑↑↑ 同学疑问：搜集的 path 应该得是契合回文子串规则，才能加入到 result[] 数组，怎么能直接就把 path 放进 result ？

其实咱们是将判别回文的逻辑放到单层查找的逻辑里边

在递归函数里边的for循环中，如何表明切开的子串？ 这是一个难点

答：startIndex 是切开线，那么切开的字串便是 [startIndex, i] 这个左闭右闭的区间。

i每向后移动一位，就代表一个子串，再向后移动，就代表一个子串，这样startIndex到i之间便是递归查找过程中不断查找的规模。

知道了子串的规模之后，就要判别它是不是回文。

vector<int> path; //寄存契合条件的单个组合（途径）
vector<vector<int>> result; //寄存组合调集
void backtracking(const string& s, int startIndex) {
  //停止条件
  if (startIndex >= s.size()) { //阐明现已到了叶子节点  (其实 == 就现已算切开到结尾了)
    result.push_back(path);
    return;
   }
  //单层查找的逻辑
  for (int i = startIndex; i < s.size(); i++) {
    //(判别切开的子串是不是回文串，若是，放到path数组里)
    if (isPalindrome(s, startIndex, i)) { //假如是回文
      path.push_back(子串);
     }
    else { //不是回文，for循环进入下一个i
      continue;
     }
    backtracking(s, i + 1); //递归
    path.pop_back(); //回溯
    return;
   }
}

AC代码： （中心代码形式）

class Solution {
private:
  vector<string> path; //寄存契合条件的单个组合（途径）
  vector<vector<string>> result; //寄存组合调集
  void backtracking(const string& s, int startIndex) {
    //停止条件
    if (startIndex >= s.size()) { //阐明到叶子节点
      result.push_back(path);
      return;
     }
    //单层查找的逻辑
    for (int i = startIndex; i < s.size(); i++) {
      if (isPalindrome(s, startIndex, i)) { //若是回文
        //获取[startIndex, i]在s中的子串
        string str = s.substr(startIndex, i - startIndex + 1);
        path.push_back(str);
       }
      else { //若不是回文  (for循环进入下一个i)
        continue;
       }
      backtracking(s, i + 1); //递归
      path.pop_back(); //回溯
      //return;  (不要return)
     }
   }
  bool isPalindrome(const string& s, int start, int end) {
    for (int i = start, j = end; i < j; i++, j--) {
      if (s[i] != s[j]) {
        return false;
       }
     }
    return true;
   }
public:
  vector<vector<string>> partition(string s) {
    result.clear();
    path.clear();
    backtracking(s, 0);
    return result;
   }
};