39.组合总和

标题链接:39.组合总和

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

难度指数:

Q:假如调集里边有0,你还重复选取,那不就死循环了吗?

A:不必担心,组合里边的元素都是正整数

树形结构

Day23 回溯算法:39.组合总和   40.组合总和Ⅱ   131.分割回文串

本题用 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循环的遍历

树形结构

Day23 回溯算法:39.组合总和   40.组合总和Ⅱ   131.分割回文串

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.组合总和Ⅱ

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

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

难度指数:

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

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

代码思路:

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

(说人话:使用过的元素不再使用,避免重复)要了解这道题的精华。

  • 树层去重
  • 树枝去重

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

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

想要去重需求先进行排序

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

树形结构

Day23 回溯算法:39.组合总和   40.组合总和Ⅱ   131.分割回文串

去重的关键在 树层去重

一维数组 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[] 这个调集进行排序。

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

Day23 回溯算法:39.组合总和   40.组合总和Ⅱ   131.分割回文串

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.切开回文串

难度指数:

Day23 回溯算法:39.组合总和   40.组合总和Ⅱ   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;
   }
};