首页 计算机科学 算法 LeetCode

# 组合总和

题目链接🔗

本题的搜索过程抽象成如下树形结构：

Alt text

因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过 target，就返回！

  1. 确定回溯函数参数和返回值

依然是定义两个全局变量，二维数组 result 存放结果集，数组 path 存放符合条件的结果。

sum 来统计单一结果 path 里的总和，startIndex 来控制 for 循环的起始位置。

  1. 确定终止条件

sum==targetsum == target 的时候，需要收集结果，sum>targetsum > target 的时候直接返回。

  1. 单层搜索的逻辑

单层 for 循环依然是从 startIndex 开始，搜索 candidates 集合。

但元素是可重复的，因此下一次搜索还是从 i 开始而不是 i+1。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i); // 不用 i+1 了，表示可以重复读取当前的数
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};
# 剪枝优化
对于 sum 已经大于 target 的情况，依旧需要进入下一层递归进行判断。
如果已经知道下一层的 sum 会大于 target 了，就没有必要进入下一层递归。
可以在 for 循环的搜索范围上进行限制。
对总集合排序之后，如果下一层的 sum（就是本层的 sum + candidates [i]）已经大于 target，就可以结束本轮 for 循环的遍历。
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)
# 组合总数 II
题目链接🔗
本题难点在于集合有重复元素，但还不能有重复的组合，涉及搜索过程中去重的过程。
组合问题可以抽象为树形结构，那么 “使用过” 在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。
元素在同一个组合内是可以重复的，但两个组合不能相同。
所以我们要去重的是同一树层上的 “使用过”，同一树枝上的都是一个组合里的元素，不用去重。
另外树层去重的话要对数组排序。
Alt text
  1. 确定回溯函数的参数和返回值
全局变量 path 和 result 存放符合条件的集合和结果。
sum 来统计单一结果 path 里的总和，startIndex 来控制 for 循环的起始位置。
需要一个 bool 型数组 used，用来记录同一树枝上的元素是否使用过。
  1. 终止条件
sum==targetsum == target 的时候，需要收集结果，sum>targetsum > target 的时候直接返回。
  1. 单层搜索逻辑
如果candidates[i]==candidates[i−1]candidates[i] == candidates[i - 1] 并且used[i−1]==falseused[i - 1] == false，就说明：前一个树枝，使用了candidates[i−1]candidates[i - 1]，也就是说同一树层使用过candidates[i−1]candidates[i - 1]。
此时 for 循环里就应该做 continue 的操作。
Alt text
可以看出在candidates[i]==candidates[i−1]candidates[i] == candidates[i - 1] 相同的情况下：
  • used[i−1]==trueused[i - 1] == true，说明同一树枝candidates[i−1]candidates[i - 1] 使用过
  • used[i−1]==falseused[i - 1] == false，说明同一树层candidates[i−1]candidates[i - 1] 使用过
因为同一树层used[i−1]==falseused[i - 1] == false 才能表示，当前取的candidates[i]candidates[i] 是从candidates[i−1]candidates[i - 1] 回溯而来的。
而used[i−1]==trueused[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上。
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            //used [i - 1] == true，说明同一树枝 candidates [i - 1] 使用过
            //used [i - 1] == false，说明同一树层 candidates [i - 1] 使用过
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used); // 和 39. 组合总和的区别 1，这里是 i+1，每个数字在每个组合中只能使用一次
            used[i] = false;
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        path.clear();
        result.clear();
        // 首先把给 candidates 排序，让其相同的元素都挨在一起。
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0, used);
        return result;
    }
};
或者用 startIndex 来去重也是可以的。
class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    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);
            sum -= candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};
# 分割回文串
题目链接🔗
本题涉及两个问题：
  1. 如何判断是回文串
  2. 切割问题，有不同的切割方式
切割问题类似组合问题。例如对于字符串 abcdef：
  • 组合问题：选取一个 a 之后，在 bcdef 中再去选取第二个，选取 b 之后在 cdef 中再选取第三个.....。
  • 切割问题：切割一个 a 之后，在 bcdef 中再去切割第二段，切割 b 之后在 cdef 中再切割第三段.....。
Alt text
递归用来纵向遍历，for 循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
  1. 确定回溯函数参数和返回值
全局变量数组 path 存放切割后回文的子串，二维数组 result 存放结果集。
参数还需要 startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。
  1. 终止条件
从树形结构图上可以看出，切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。
在处理组合问题的时候，递归参数需要传入 startIndex，表示下一轮递归遍历的起始位置，这个 startIndex 就是切割线。
  1. 单层搜索的逻辑
在 for (int i = startIndex; i < s.size(); i++) 循环中，我们 定义了起始位置 startIndex，那么[startIndex,i][startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在 vector<string> path 中，path 用来记录切割过的回文子串。
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;
    }
};
# 复原 IP 地址
题目链接🔗
和切割回文串一样，本题也是切割问题。
Alt text
  1. 回溯函数参数和返回值
定一个全局变量 result 记录结果。
startIndex 一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
本题我们还需要一个变量 pointNum，记录添加逗点的数量。
  1. 终止条件
本题明确要求只会分成 4 段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
pointNum 表示逗点数量，pointNum 为 3 说明字符串分成了 4 段了。
然后验证一下第四段是否合法，如果合法就加入到结果集里
  1. 单层搜索逻辑
在 for (int i = startIndex; i < s.size(); i++) 循环中[startIndex,i][startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。
如果合法就在字符串后面加上符号。表示已经分割。
如果不合法就结束本层循环，如图中剪掉的分支：
Alt text
然后就是递归和回溯的过程：
递归调用时，下一层递归的 startIndex 要从 i+2 开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量 pointNum 要 +1。
回溯的时候，就将刚刚加入的分隔符。删掉就可以了，pointNum 也要 - 1。
class Solution {
private:
    vector<string> result;// 记录结果
    //startIndex: 搜索的起始位置，pointNum: 添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为 3 时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进 result 中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在 i 的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为 i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法，直接结束本层循环
        }
    }
    // 判断字符串 s 在左闭又闭区间 [start, end] 所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0 开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于 255 了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};