Day27|Leetcode 39. 组合总和 Leetcode 40. 组合总和 II Leetcode131. 分割回文串

Leetcode 39. 组合总和

题目链接 39 组合总和

本题目和前面的组合问题差不多，只不过这里能重复选取数字，还是要注意组合的定义，交换数字顺序还是算一个组合，所以这里还是用我们的startIndex来记录取的数字到哪里了，下面上代码：

class Solution {
    private:
    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++){
            //其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。
            //对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。
            path.push_back(candidates[i]);
            sum+=candidates[i];
            backtracking(candidates, target,sum,i);// 不用i+1了，表示可以重复读取当前的数
            sum-=candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());//从小到大排序
backtracking(candidates, target,0,0);
        return result;
    }
};

Leetcode 40. 组合总和 II

题目链接 40 组合总和 II

本题目的要求是每个集合的元素只能出现一次，所以说我们需要去重，如何去重才是本题目的关键，其他的地方和上面的题目一样，我们将回溯函数转化为树状图，其实可以分为两个去重，一个是树枝去重，一个是树层去重，下面用一个图片来体现如何去重：

（默认sort排序）在树枝上的去重我们已经完成，我们再看在树层上，取第二个1的时候下面的情况1，2，已经在取第一个1时下面的情况中涉及到了，因为，第一个1后面既有重复的第二个1，也有第二个1后面的元素，所以第一种1一定会包含第二种1的情况。去重我们就完成了，下面直接上代码：

class Solution {
    private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking (vector<int>& candidates,int target,int sum,int startIndex,vector<bool>& used){
        if(sum==target){
            result.push_back(path);
            return ;
        }
        for(int i=startIndex;i<candidates.size()&&sum+candidates[i]<=target;i++){
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){
                continue;
            }
 
            path.push_back(candidates[i]);
            used[i] = true;
            sum+=candidates[i];
            backtracking(candidates,target,sum,i+1,used);
            sum-=candidates[i];
            used[i] = false;
            path.pop_back();
 
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(),false);初始化
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0,used);
        return result;
    }
};

Leetcode131. 分割回文串

题目链接 131 分割回文串

上面的题目都是组合类的，从这个题目开始就进入分割类题目了，其实组合和分割是一个意思，同样能用树状结构来解决。

除此之外还有几个需要注意的点，第一个就是将子字符串传递给path，用到了substr （s.substr(pos, len)，pos默认值为0，len的默认值是s.size() - pos）转化字符串，第二个就是回文字符串的判断，最后就是回溯函数的模板了，上代码：

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)){
                string str = s.substr(startIndex,i-startIndex+1);//转化子字符串
                path.push_back(str);
            }else{
                continue;
            }
            backtracking(s,i+1);//递归
            path.pop_back();//回溯
        }
    }
    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) {
        backtracking(s,0);
        return result;
    }
};

end，状态不佳啊