关于算法:算法数据结构-回溯中重复元素与分割问题分析总结

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

• 组合总和
  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;        
    }
};