526互联

算法学习Day26组合总和、分割回文串

发布时间 2024-01-13 17:58:28作者: HQWQF

Day26组合总和、分割回文串

By HQWQF 2024/01/13

笔记

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1：

  • 输入：candidates = [2,3,6,7], target = 7,
  • 所求解集为： [ [7], [2,2,3] ]

回溯法

这道题和216.组合总和III类似，但是可以重复包含同一个元素，所以我们递归退出条件不能是path的长度，而应该是path的元素总和，大于则target值就退出，等于target值就加入结果后退出。

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int target, int sum,vector<int> candidates,int startIndex) {
        if(sum > target){return;}
        else if(sum == target){result.push_back(path);return;}

        for (int i = startIndex; i < candidates.size(); i++) {
            path.push_back(candidates[i]); // 处理节点
            sum += candidates[i];
            backtracking(target, sum, candidates,i); // 递归
            sum -= candidates[i];
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(target,0, candidates,0);
        return result;
    }
};

剪枝

值得注意的是，在sum 已经大于target值时，我们需要再进入一层递归才会返回，进入递归的性能成本是比较大的，我们可以在在sum加加后直接判断，这样就不用进入递归了。

其实，我们可以先对candidates进行排序，然后直接在for循环处判断sum 加过元素值后是否大于target，大于的话也不用考虑当前元素后面的元素了：

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int target, int sum,vector<int> candidates,int startIndex) {
         if(sum == target){result.push_back(path);return;}

        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            path.push_back(candidates[i]); // 处理节点
            sum += candidates[i];
            backtracking(target, sum, candidates,i); // 递归
            sum -= candidates[i];
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        sort(candidates.begin(), candidates.end());
        backtracking(target,0, candidates,0);
        return result;
    }
};

40.组合总和II

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

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

说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

  • 示例 1:
  • 输入: candidates = [10,1,2,7,6,1,5], target = 8,
  • 所求解集为:
[

  [1, 7],

  [1, 2, 5],

  [2, 6],

  [1, 1, 6]

]

回溯法

首先的一个想法是将求出的结果进行去重，但是这样时间太长。

我们需要在得出结果的过程中去重，为了避免得出相同的解，我们可以先对candidates 进行排序，这样candidates 中相同的元素就会相邻，我们在循环时做一个判断i > 0 && candidates[i] == candidates[i - 1]就可以避免寻中相同的元素。

但是注意我们要避免的重复是在树的同一层出现的重复，在解的不同位的重复是可以的，只是这样判断就会导致解的不同位的重复不被通过。

这种情况发生在刚进入树的下一层时（因为candidates[i] == candidates[i - 1]失效本质是因为当前candidates[i - 1其实并不在当前层待选择的元素中），此时的candidates[i - 1]包含在解中。

所以若当前的candidates[i - 1]不包含在解中，说明是同一层的重复。

所以我们可以维护一个bool数组useing，如果当前解包含candidates 中某位的元素，那useing对应位就为true，反之为false。以此判断candidates[i - 1]是否包含在解中。

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int target, int sum,vector<int> candidates,int startIndex,vector<bool> useing) {
         if(sum == target){result.push_back(path);return;}

        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && useing[i - 1] == false) {
                continue;
            }   
            path.push_back(candidates[i]); // 处理节点
            sum += candidates[i];
            useing[i] = true;
            backtracking(target, sum, candidates,i + 1,useing); // 递归
            sum -= candidates[i];
            useing[i] = false;
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }    
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        vector<bool> useing(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        backtracking(target,0, candidates,0,useing);
        return result;
    }
};

其实在发现了 candidates[i] == candidates[i - 1]的情况发生在刚进入树的下一层这个事实后，我们可以想到，刚进入树的下一层时，i == startIndex，所以使用i > startIndex && candidates[i] == candidates[i - 1]就可以判断同层重复了。

 Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            // 要对同一树层使用过的元素进行跳过
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i + 1); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        path.clear();
        result.clear();
        // 首先把给candidates排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }

131.分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

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

示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]

回溯法

我们可以从字符串的左边开始砍字符串，若砍完左边的段是回文串就加入解中，接着对右边的段砍，然后重复这个过程。

判断是否为回文串可以用双指针法。

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path; // 放已经回文的子串
    void backtracking (const string& s, int startIndex) {
        // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
        if (startIndex >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            //判断砍完左边的段是不是回文串
            if (isPalindrome(s, startIndex, i)) {   // 是回文子串
                // 获取[startIndex,i]在s中的子串
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            } else {                                // 不是回文，跳过
                continue;
            }
            backtracking(s, i + 1); // 寻找i+1为起始位置的子串，接着对右边的段砍
            path.pop_back(); //砍到头了就全部退出
        }
    }
    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;
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
};