之前做题给的题解都太混乱了，我决定好好按照思路写题解。

题目1 39. 组合总和

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

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

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

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

思路

1. 确定递归参数

辅助对象

path用于保存回溯临时结果

result用于保存所有的结果

backtrack参数

target是上次回溯的计算结果

curIndex表示当前回溯从哪一个元素开始

candidates为题目给出的元素数组

2. 确定递归终止边界

因为在回溯过程中的每一个target减去当前的candidates[i]，因此当且仅当target == 0时终止当前回溯，并保存结果。

3. 单层搜索的逻辑

因为题目中指出每个元素可以使用多次，因此，在调用backtrack时的curIndex参数要赋予i而不是下一个元素i+1。每一轮遍历要进行向path放入元素并且target减去当前元素，之后调用backtrack回溯，回溯结束后将放入的元素删除并且target恢复成原值。

代码

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtrack(int target, int curIndex, vector<int>& candidates)
    {
        if(target == 0)
        {
            result.push_back(path);
            return;
        }
        for(int i = curIndex; i < candidates.size() && candidates[i] <= target; i++)
        {
            target -= candidates[i];
            path.push_back(candidates[i]);
            backtrack(target, i, candidates);
            target += candidates[i];
            path.pop_back();
        }

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrack(target, 0, candidates);
        return result;
    }
};

题目2 40. 组合总和 II

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

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

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

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

思路

这道题的思路和上道题类似，不同的是每个元素只允许使用一次且解集合不能重复，因此在循环中要注意使用一个元素后就要排除掉所有相同的元素避免解集合重复。回溯三部曲如下：

1. 确定回溯参数

path为保存临时结果的数组对象

result为保存最终结果的数组对象

candidates为题干数组

target为当前的目标

curIndex为当前回溯的起点

2. 确定回溯终止条件

当且仅当target为零时将临时结果path保存到result中

        if(target == 0)
        {
            result.push_back(path);
            return ;
        }

3. 单层搜索的逻辑

这里要注意的是当前将元素candidates[i]进行完放入取出path后要将所有同名的元素排除，因此也需要对candidates进行排序处理。

    for(int i = curIndex; i < candidates.size() && candidates[i] <= target; i++)
    {
        path.push_back(candidates[i]);
        target -= candidates[i];
        backtrack(candidates, target, i + 1);
        target += candidates[i];
        path.pop_back();
        //去重
        while(i + 1 < candidates.size() && candidates[i] == candidates[i + 1])
        {
            i++;
        }
    }

代码

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

题目3 131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是

回文串

。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

思路

这道题关键点在如何切子串，一个回溯里会遍历整个子串，在每次遍历时会对当前的前一部分子串进行回文串的判断，如果是回文串则加入临时解集中，并继续调用回溯函数。其回溯三部曲如下：

1. 回溯参数

path临时解集

result最终结集

isRound用于判断字符串是否为回文串

backtracking回溯函数，s为当前要题目的字符串，curIndex为当前需要处理的子串开头位置

2.回溯终止条件

在backtracking中当当前要处理的位置和题目的字符串一致时表明path的解集为一个结果，将此结果保存到result中。

    if(curIndex == s.size())
    {
        result.push_back(path);
        return ;
    }

3. 单层搜索逻辑

在循环中每一次要对当前处理的子串进行判断，判断子串是否为回文串，若不是回文串则continue判断下一个子串；若是回文串则将当前子串加入path中并调用回溯进行剩余子串的判断与入path，当回溯调用结束后将当前子串从path中去除并进行下一轮循环。

代码

class Solution {
public:
    vector<string> path;
    vector<vector<string>> result;
    bool isRound(string& str)
    {
        for(int i = 0; i < str.size() / 2; i++)
        {
            if(str[i] != str[str.size() - i - 1])
                return false;
        }
        return true;
    }
    void backtracking(string& s, int curIndex)
    {
        if(curIndex == s.size())
        {
            result.push_back(path);
            return ;
        }
        for(int i = curIndex; i < s.size(); i++)
        {
            string tmp = s.substr(curIndex, i - curIndex + 1);
            //字串非环则不满足条件，返回
            if(!isRound(tmp))
                continue;
            path.push_back(tmp);
            backtracking(s, i + 1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return result;
    }
};