JLUVicent

39组合总和&40组合总和II&131分割回文串

 
  • 2023年 03月13日
  • 0 阅读

day27

39.组合总和

题目链接：39. 组合总和

解题思路：参考 视频

使用递归三部曲，首先定义两个变量一个存储结果二维数组，一个存储路径，然后定义函数的参数，一共有四个，一个记录数组，一个记录目标值，一个记录sum值，一个记录开始变量。中间有递归和回溯的过程。

class Solution {
public:

    // 全局变量存放结果
    vector<int> path;
    vector<vector<int>> result;

    // 确定返回值和参数
    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() && sum+candidates[i]<=target; i++){
            // 保存结果
            path.push_back(candidates[i]);
            sum += candidates[i];
            // 递归
            backtracking(candidates,target,sum, i);	//这块不加1是因为题目中说可以无限制重复选取
            //回溯
            path.pop_back();
            sum -= candidates[i];
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int sum = 0;
        int startIndex = 0;
        sort(candidates.begin(),candidates.end());  //剪枝需要排序
        backtracking(candidates,target,sum,startIndex);
        return result;
        
    }
};

40.组合总和II

题目链接：40. 组合总和 II

解题思路：参考 视频

去重之前需要对nums进行排序，for控制横向,递归控制纵向，其他的和之前的组合问题一样

40.组合总和II

class Solution {
public:

    // 存储结果
    vector<int> path;   //存储路径
    vector<vector<int>> result;     //存储最终结果
    
    // 确定返回值和参数
    void backtracking( vector<int>& nums,int target, int sum, int startIndex,vector<bool>& used){
        // 确定终止条件
        if( sum > target ) return ;
        if( sum == target ){
            result.push_back(path);
            return;
        }

        // 确定单层逻辑
        for( int i = startIndex; i < nums.size() && sum+nums[i] <=target; i++){
            // 去重操作
            if( i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;  //前一个元素没有被用过
            path.push_back(nums[i]);    //添加元素
            sum += nums[i];
            used[i] = true;
            backtracking( nums,target,sum,i+1,used);
            sum -= nums[i];
            used[i] = false;
            path.pop_back();
        }
    }

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

131.分割回文串

题目链接：131. 分割回文串

解题思路：参考 视频

首先确定终止条件，这里startIndex可以理解为切割线，只要切割线大于等于s.size()也就是切割线到最后了，就将path的结果加入result，回文串用双指针判断，其他模板与组合之前的回溯模板相同。

class Solution {
public:

    // 判断回文串
    bool isPalinrome(const string& s,int startIndex, int i){
        int left = startIndex;
        int right = i;
        while( left <= right){
            if(s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    // 递归函数
    vector<string> path;
    vector<vector<string>> result;
    void backTracking(const string&s,int startIndex){
        // 确定终止条件
        if( startIndex >= s.size() ){   //如果切割点到了size()这，就加入，判断回文逻辑放下面
            result.push_back(path);
            return;
        }

        for( int i = startIndex; i < s.size(); i++){
            if( isPalinrome(s,startIndex,i) ){  //判断是否回文
                string str = s.substr(startIndex , i - startIndex + 1); // 开始startIndex, 第二个参数是截取的数量
                path.push_back(str);
            }
            else{ continue;}
            backTracking(s,i+1);
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        backTracking( s,0);
        return result;
    }
};
搜索