代码随想录算法训练营第二十九天 | 39. 组合总和、40.组合总和II、131.分割回文串

39. 组合总和

题目链接/文章讲解：代码随想录

视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili

解题思路

这里和组合不同的是元素可以重复选取，其实也就是注意startindex的位置就可以，深度控制是由k的值来进行的

剪枝操作

剪枝一般都是在for循环上做操作，因为多了一些分支

而这题，我们只需要将数组排序后，例如235，和为4，当2+3已经大于4了，就没必要去遍历5了，因此在for循环中多加个判断条件即可

class Solution {
private:
vector<int> path;
vector<vector<int>> result;
int sum =0;

public:
    void backtracking(vector<int>& candidates, int sum , int target , int startIndex)
    {
        if(sum == target)
        {
            result.push_back(path);
            return;
        }
        for(int i = startIndex ; i<candidates.size()&& sum + candidates[i] <=target;i++)   //将数组排序后，如果这个数和另一个数相加已经大于taget了，那么后面的数也就没有必要继续遍历了
        {
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates,sum,target,i);
            path.pop_back();
            sum-=candidates[i];
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
               //对数组进行排序，方便后面的剪枝操作
                sort(candidates.begin(),candidates.end());
                backtracking(candidates,sum,target,0);
                return result;
    }
};

40.组合总和II

题目链接/文章讲解：代码随想录

视频讲解：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II_哔哩哔哩_bilibili

解题思路

这道题中是有重复元素的，去重我们考虑，树枝去重（深）和树层去重（宽）

这题的去重逻辑，其实和三数之和很像，我们排完序后，在树枝上，我们取重复元素是可以的，但是在树层，在遇到相同的，也就是已经走过的路了，那就不要再走了，直接剪枝就可以了，但是我们如何去判断这是在树层上，还是在树枝上？我们只需要用uesd数组，当i-1的位置为0，说明在树层上，i-1的位置为1，说明在树枝上。

后面基本回溯的去重写法都是这个！！！非常重要

class Solution {
private:
vector<vector<int>> result;
vector<int> path;
public:
   void backtracking(vector<int>& candidates, int target, int sum , int startIndex , vector<int>& used)
   {
        if(sum == target)
        {
            result.push_back(path);
            return;
        }
        for(int i= startIndex; i<candidates.size() && sum + candidates[i] <= target; i++)
        {
              if(i>0 &&candidates[i]== candidates[i-1] && used[i-1]==0) continue;   //如果前一个used为1的话，表明在树枝上
              path.push_back(candidates[i]);
              sum += candidates[i];
              used[i] = 1 ;
              backtracking(candidates,target,sum, i+1,used);
              used[i] = 0 ;
              sum -= candidates[i];
              path.pop_back();
        }
   }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
                vector<int> used(candidates.size(),0);
                sort(candidates.begin(),candidates.end());
                backtracking(candidates,target,0,0 , used);
                return result;
    }
};

131.分割回文串

代码随想录

视频讲解：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！_哔哩哔哩_bilibili

解题思路

本题主要要理解的是如何画树形结构

其本质和组合问题是一样的，从图上说明更明确

这里我们进行切割的话，是使用startIndex来进行标记的，而在横向的切割中，是用i去寻找下一个切割点的，因此我们截取字符串也是从[stratIndex,i]去截取的

class Solution {
private:
vector<string> path;
vector<vector<string>> result;
    bool isHuiWenStr(const string& s, int a, int b)
    {
        //利用双指针来判断回文串
        for(int i=a,j=b;i<=j;i++,j--)
        {
            if(s[i]!=s[j])
                return false;
        }
        return true;
    }
    
    void backtracking(const string& s, int startIndex)  //这里是用startIndex来分割字符串的，本质和组合问题是一样的
    {
        //终止条件，因为是用startindex来分割的，那么当startindex的位置已经位于字符串最后说明分割完了
        if(startIndex >= s.size())
        {
            result.push_back(path);
            return;
        }
        //单层处理逻辑
        for(int i= startIndex; i< s.size();i++)
        {
            if(isHuiWenStr(s,startIndex,i))
            {
                string str = s.substr(startIndex,i-startIndex+1);    //截取字符串函数，变量分别为索引和个数
                path.push_back(str);
            }
            else
                continue;
            backtracking(s,i+1);
                path.pop_back();
        }
        
    }
public:
    vector<vector<string>> partition(string s) {
              backtracking(s,0);
            return result;
    }
};