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

2024-01-08 13:33:44

39. 组合总和

题目链接:39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

文章讲解/视频讲解:https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

思路

这道题目和之前做过的组合III比较类似,只不过这里是允许将元素重复加入组合的。利用回溯三部曲来分析。

第一步,确定回溯函数的参数,我们需要指定当前已有元素的组合path,当前已经遍历到的下标starti,组合中元素和与target的差值left。

第二步,确定什么时候回溯结束,在这里,因为元素可以重复添加,因此判断依据是left = 0。

第三步,遍历的过程。横向遍历的过程主要是按序遍历这个整数数组candidates,纵向遍历的过程则是递归遍历组合的下一个待添加元素。需要注意的是,因为题目允许组合中有重复元素,因此我们在递归遍历组合下一个元素时,下标不需要+1。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> path;
        backtracing(path, 0, target, candidates);
        return results;
    }

    void backtracing(vector<int>& path, int starti, int left, const vector<int>& candidates){
        if(left == 0){
            results.push_back(path);
            return;
        }
        for(int i = starti;i<candidates.size();i++){
            int cur = candidates[i];
            if(cur <= left){
                path.push_back(cur);
                backtracing(path, i, left - cur, candidates);
                path.pop_back();
            }
        }
    }
};

40.组合总和II

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

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次

**注意:**解集不能包含重复的组合。

文章讲解/视频讲解:https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html

思路

这道题中要求数组中的每个元素只能使用一次,而且组合不能重复。注意,不同元素中可能数值相同。

为了便于去重,我们先将candidates数组排序,然后利用回溯三部曲来分析解决,其中去重操作可以参考之前三数之和中的方法。

第一步,确定回溯函数的参数,我们需要指定当前已有元素的组合path,当前已经遍历到的下标starti,组合中元素和与target的差值left。

第二步,何时结束回溯,当left等于0的时候。

第三步,遍历过程,横向遍历的过程主要是按序遍历这个整数数组candidates,纵向遍历的过程则是递归遍历组合的下一个待添加元素。这里在递归遍历下一个元素时,需要将下标+1。参考三数之和中的去重方法,我们在横向遍历的过程中,如果当前下标的元素和上一个下标的元素值相同,则跳过该元素,因为此时获得的组合结果一定是重复的。另外,因为我们已经将candidates数组排好了序,在横向遍历时,如果candidates[i] > left,就可以提前剪枝。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        backtracing(path, 0, target, candidates);
        return results;
    }

    void backtracing(vector<int>& path, int starti, int left, const vector<int>& candidates){
        if(left == 0){
            results.push_back(path);
            return;
        }

        for(int i = starti;i<candidates.size() && candidates[i] <= left;i++){
            if(i > starti && candidates[i] == candidates[i - 1]) continue;
            path.push_back(candidates[i]);
            backtracing(path, i + 1, left - candidates[i], candidates);
            path.pop_back();
        }
    }
};

131.分割回文串

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

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

文章讲解/视频讲解:https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html

思路

采用回溯的三部曲来解决。

首先确定回溯函数的参数值,我们需要一个存储当前回文串数组的集合path,当前已经遍历到的下标starti。

什么时候回溯停止?当starti等于字符串s的长度时,表面当前已经遍历到了s的末尾。此时,需要做一个判断,如果path中所有回文串的长度等于s的长度,即path把s中的所有元素都包括了,那么我们就找到了一种回文串划分,并将这个划分添加进结果中。

如何遍历?我们每次回溯的目标是找到一种划分,这种划分得到的所有子串都是回文子串。横向遍历的过程是找到划分中当前的分隔,纵向遍历的过程是找到下一个分隔。怎么去找这样的分隔呢?我们需要在横向遍历的时候采用两层遍历,i指向当前分隔的起点,j指向当前分隔的终点。如果i, j之间能够构成一个回文串,则继续纵向遍历下一个分隔,此时将starti设置为j + 1。

C++实现

class Solution {
public:
    vector<vector<string>> results;
    vector<vector<string>> partition(string s) {
        vector<string> path;
        backtracing(path, 0, s);
        return results;
    }

    void backtracing(vector<string>& path, int starti, const string& s){
        if(starti == s.size()){
            int length_sum = 0;
            for(int i = 0;i<path.size();i++) length_sum += path[i].size();
            if(length_sum == s.size()) results.push_back(path);
            return;
        }

        for(int i = starti;i<s.size();i++){
            for(int j = i;j<s.size();j++){
                if(isPalindrome(s, i, j)){
                    string cur = s.substr(i, j - i + 1);
                    path.push_back(cur);
                    backtracing(path, j + 1, s);
                    path.pop_back();                    
                }
            }
        }
    }

    bool isPalindrome(const string& s, int left, int right){
        while(left < right){
            if(s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135454164
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。