组合问题（分割字符串）

131. 分割回文串 - 力扣（LeetCode）

class Solution {
private:vector<vector<string>>result;vector<string>path;void backtracking(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(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;}
};

分割回文子串也是一道组合问题，构造树形结构，使每层分割每一个元素，下一层分割为剩余元素中的每一个元素。

目标结果在叶子节点上，和组合问题的逻辑相同，将每一个树的遍历路径存在path数组中，如果遇到不符合目标值的，就continue出去，所以符合条件的路径都存在了path数组中。

终止条件：当startIndex>=s.size()，也就是到达了叶子节点时，将path数组的值push进result数组中。startIndex定义的时分割的是第几个元素。

单层递归逻辑：从上一层分割的第startIndex元素开始，向后遍历直到结尾，判断是否为回文子串，如果是，则提取从startIndex开始后i-startIndex+1个元素（std::substr()函数：前一个值值从字符串的第几个元素开始取元素，后一个值指取几个元素），将所得元素放入path数组中，再向下一层递归，i的值加一，也就是将分割的值向后进一位。

回溯逻辑：因为要回溯到上一层去分割不同元素，所以要将存入的值pop出。

判断回文子串逻辑，定义一个返回值是布尔值的函数，传入字符串，分割开始值和字符串结尾值，遍历字符串开始和字符串结束是否相同，相同则为回味回文子串。

组合问题（二叉树，递归，回溯算法）-CSDN博客