leetcode_day26

今日任务：

• 39. 组合总和 medium
• 40. 组合总和Ⅱ medium
• 131. 分割回文串 medium

39. 组合总和

题目：

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

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

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

思路：

递归挨个选取就行，选了一个之后递归下一个，起点不变，如果和到了target就加入答案，可以在下一步递归前判断当前值是否已经过大了，过大则跳过实现剪枝。比较简单

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    void backtrack(vector<int> &candidate, int target, int begin) {
        if(target == 0) {
            ans.push_back(temp);
            return;
        }
        for(int i = begin;i < candidate.size();i++) {
            if(candidate[i] > target) continue;
            temp.push_back(candidate[i]);
            backtrack(candidate, target - candidate[i], i);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if(candidates.size() == 0) return {};
        backtrack(candidates, target, 0);

        return ans;
    }
};

40. 组合总和Ⅱ

题目：

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

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

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

提示:

1 <= candidates.length <= 100

1 <= candidates[i] <= 50

1 <= target <= 30

思路：

难点主要在于去重，下面举个例子来快速直观体会这道题要去什么重

对于示例：[10,1,1,7,6,1,5]、target = 8，正确结果应该是[[1,1,1,5],[1,1,6],[1,7]]。 题目中candidate中的每个数字只能用一次是关键，勿错误理解为每种数字只能用一次，示例[10,1,1,7,6,1,5]中有3个1，当选中第一个1作为解成员之一递归下去的时候，由于之前无1，所以已有的解中肯定无1，后面的两个1仍然可用，由答案可见，选中第一个1递归下去已经可以得到全部解了。

那么选中第二个1作为解成员之一递归下去后，后面还有一个1，此时含有两个1的解已经出现过了，此时需要去重。

由上可看出不能简单使用used来阻止使用使用过的下标，因为第一个1把所有解得到后，回溯取消操作会开放used，后面的1又会变得可用，去重失败

carl哥的代码思路按我理解可以叙述为：重复元素只能由排前面的重复元素使用，对于上面的示例，就是含有多个1的解只能由第一个1的递归分支得到，后面的如果还是1就不能在解里出现1。

排前面的重复即对应carl哥说法的前一个树枝，即前一个重复元素的解空间树分支。

又瞟了题解才做出来，WA了4发😭😭😭

脑子抽了没看见1 <= candidates.length <= 100，还乐呵呵地用位运算当used[]用来记录哪些下标被用了，左移右移老半天跟二傻子似的，结果不仅位运算爆long long，而且用used记录本身就是脱裤子放屁，因为我回溯传了起点begin……

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    void backtrack(vector<int> &candidate, int target, int begin) {
        if(target == 0) {
            ans.push_back(temp);
            return;
        }
        for(int i = begin;i < candidate.size();i++) {
            if(candidate[i] > target) continue;
            if(i > begin && candidate[i] == candidate[i - 1]) continue;//去重关键
            temp.push_back(candidate[i]);
            backtrack(candidate, target - candidate[i], i + 1);
            temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if(candidates.size() == 0) return {};
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0);
        return ans;
    }
};

131. 分割回文串

题目：

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

思路：

没做出来，贴出失败思路：

分割子串，想到之前做的有关题目了，至少分割操作还是比较熟悉，用迭代器构造新串就好，从首开始分割，分割长度逐渐递增，也就是回溯中的那个for循环，每个分割长度在分割前判断是否是回文串，如果是回文串就分割，不是就接着增大分割长度。

然后就卡了……没记住或者说想另辟蹊径结果弄巧成拙，没有像模板那样接着回溯下一种可能并取消当前轮次操作继续for循环。

接下来是正确思路：

仍然按照回溯模板，理清递归思路：

1. 递归参数与返回值： 返回值void， 参数应该是分割起点，确保能够递归下去接着分割之后的子串
2. 递归终止条件，如果真的分割到结尾，那么该条递归调用路线就是正确的，此时temp中即为一个答案，标准就是起点超过了终点，begin大于了string的长度
3. 递归操作：逐个尝试分割长度，合法就接着分割，不合法就跳过

carl哥这次画的解空间树很形象，如下图，失败思路想到了怎么分支，但是没想到怎么判断叶节点，具体的代码写法也写昏了头

代码

一般代码

之所以叫一般，是因为判断回文串的函数isValid每次调用都要俩指针相向而行，有很多重复操作，提高了时间复杂度

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> temp;
    bool isValid(string s, int begin, int end) {
        int left = begin, right = end;
        if(right > s.size()) return false;
        while(left <= right) {
            if(s[left++] != s[right--]) return false;
        }
        return true;
    }

    void backtrack(string &s, int begin) {
        if(begin >= s.size()) {
            ans.push_back(temp);
            return ;
        }
        for(int i = begin;i < s.size();i++) {
            if(isValid(s, begin, i)) {
                temp.push_back(string(s.begin() + begin, s.begin() + i + 1));
                backtrack(s, i + 1);
                temp.pop_back();
            }
            else continue;
            
        }
    }
    vector<vector<string>> partition(string s) {
        backtrack(s, 0);
        return ans;
    }
};

动态规划代码

使用动态规划（dynamic programming， DP）直接把所有子串是否是回文串都提前算好，这样后续判断时就只需要O(1)复杂度就可以了

动态规划状态转移方程为：

           ⌜1, i = j 

dp[i][j] = +s[i]==s[j], i = j - 1

           ㇗s[i]==s[j]ANDdp[i+1][j-1],else

不会打latex，好拉的公式，快去配置渲染器！！

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> temp;
    vector<vector<bool>> dp;

    void backtrack(string &s, int begin) {
        if(begin >= s.size()) {
            ans.push_back(temp);
            return ;
        }
        for(int i = begin;i < s.size();i++) {
            if(dp[begin][i]) {
                temp.push_back(string(s.begin() + begin, s.begin() + i + 1));
                backtrack(s, i + 1);
                temp.pop_back();
            }
            else continue;
            
        }
    }
    void isValid(string &s) {
        dp.resize(s.size(), vector<bool>(s.size(), false));//vector还得resize了才能用
        for(int i = s.size() - 1;i >= 0;i--) {
            for(int j = i;j < s.size();j++) {
                if(i + 1 == j) dp[i][j] = s[i] == s[j];
                else if(i == j) dp[i][j] = true;
                else dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1];
            }
        }
    }
    vector<vector<string>> partition(string s) {
        isValid(s);
        backtrack(s, 0);
        return ans;
    }
};