[算法数据结构] 回溯中重复元素与分割问题分析总结

这里总结昨天做的两类体型。组合总和问题中假如遇到重复元素情况和分割问题。

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