这里总结昨天做的两类体型。组合总和问题中如果遇到反复元素状况和宰割问题。

  • 组合总和
    https://leetcode.cn/problems/... 思路聚焦到再以后层，该怎么选取，对应到代码中就是回溯函数中，for 循环外面如何管制回溯函数的传入参数，使得可能反复选取自身，并且不造成反复的组合。
class Solution {public:    vector<vector<int>> result;    vector<int> path;    int sum = 0;    void backtracking(vector<int>& candidates, int target, int startIndex) {        if (sum == target) {           result.push_back(path);           return ;         }        if (sum > target) return ;        for (int i = startIndex; i < candidates.size(); i++) {            sum += candidates[i];            path.push_back(candidates[i]);            backtracking(candidates, target, i);            sum -= candidates[i];            path.pop_back();        }    }    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {        backtracking(candidates, target, 0);        return result;    }};

保障每一次回溯，startIndex 都从以后节点开始抉择，保障了可能选取到自身节点并且不反复抉择之前的节点，造成组合反复。

  • 组合总和II
    这种状况是有反复的元素，并且每一个数据只能用一次。难点在于，假使[1, 1, 5] ，target = 6如果让startIndex 等于 i + 1 就会导致反复组合[1, 5], [1, 5]。 因而须要剪枝，如何了解剪枝，跳过以后的for循环，continue。
class Solution {public:    vector<vector<int>> result;    vector<int> path;    int sum = 0;    void backtracking(vector<int>& candidates, int target, int startIndex) {        if (sum == target) {           result.push_back(path);           return ;         }        if (sum > target) return ;        for (int i = startIndex; i < candidates.size(); i++) {            if (i > startIndex && candidates[i] == candidates[i - 1]) {                continue;            }            sum += candidates[i];            path.push_back(candidates[i]);            backtracking(candidates, target, i + 1);            sum -= candidates[i];            path.pop_back();        }    }    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {        sort(candidates.begin(), candidates.end());        backtracking(candidates, target, 0);        return result;    }};

在for循环语句中判断是否要continue是要害。留神有一个与上（i > startIndex）也非常要害，意思是指在同一层上在第一个节点之后的节点的判断。其余代码一样。

  • 宰割回文串
    和组合问题有相似之处，通过设定startIndex来管制所要选取的子字符串，startIndex = 0 代表将第一个字符串分进来，决定了树状构造中每一层的第一个抉择后果。增加了一层判断：如果为字符串是回文串，那么持续回溯，如果不是就continue.
class Solution {public:    vector<vector<string>> result;    vector<string> path;    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;    }    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);                backtracking(s, i + 1);                path.pop_back();            }             else {                continue;            }        }    }    vector<vector<string>> partition(string s) {        backtracking(s, 0);        return result;            }};