理论基础

回溯法的本质是穷举，它在解决以下问题中经常会被用到。

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

组合和排列的区别

• 组合不强调元素顺序，对于组合来说{1,2}和{2,1}在是同一个集合
• 排列强调元素顺序，对于排列来说{1,2}和{2,1}是两个集合

如何理解回溯法

for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

总结：在递归中使用for循环

模版

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合经典题目

77 组合

77. 组合 – 力扣（LeetCode）

代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(int n, int k, int startindex) {
        if (path.size() == k) {
            res.push_back(path);
            return ;
        }
        for (int i = startindex; i < n + 1; i++) {
            path.push_back(i); 
            backtracking(n, k, i + 1); 
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) { 
        int startindex = 1;
        backtracking(n, k, startindex);
        return res;
    }
};

剪枝优化

我们已经知道回溯法本质上是一种穷举，那么穷举的时候有没有办法能够优化性能呢？让我们考虑n=4，k=4的场景，我们不难发现有很多没有必要进行回溯的步骤，如下图：

那么映射到代码上，由于是在横向便利时进行剪枝，我们要控制的是for循环的条件。

原本的for循环代码

vector<int> path;
...
for (int i = startindex; i < n + 1; i++) {
    /* ... */
}

考虑到剪枝操作，做如下修订

vector<int> path;
...
for (int i = startindex; i <= n-(k-path.size()) + 1; i++) {
    /* ... */
}

• path.size()：已经找的个数
• k-path.size()：还需要找的个数

所以 [x, n] 的数组长度大于等于k-path.size()才有继续搜索的必要，那么就有n-x+1>=k-path.size();故而

x <= n-(k-path.size())+1

216 组合总和III

216. 组合总和 III – 力扣（LeetCode）

思路

与77的不同是递归结束的条件，只需要加上sum为n即可。

17 电话号码的字母组合

17. 电话号码的字母组合 – 力扣（LeetCode）

思路

本题的每一个数字代表不同的集合，所以实际上是不同集合之间的组合问题

1. 多了一层数字和字母的映射
2. 需要处理入参

代码

class Solution {
private:
    const string letterMap[10] = {
        "",     /* 0 */
        "",     /* 1 */
        "abc",  /* 2 */
        "def",  /* 3 */
        "ghi",  /* 4 */
        "jkl",  /* 5 */
        "mno",  /* 6 */
        "pqrs", /* 7 */
        "tuv",  /* 8 */
        "wxyz", /* 9 */
    };
    vector<string> res;
    string path;
public:
    void back_tracking(const string& digits, int index) {
        if (index == digits.size()) {
            res.push_back(path);
            return ;
        }

        int key = digits[index] - '0';
        string letter = letterMap[key];
        for (int i = 0; i < letter.size(); i++) {
            path.push_back(letter[i]);
            back_tracking(digits, index + 1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return res;
        }
        back_tracking(digits, 0);
        return res;
    }
};

39 组合总和

39. 组合总和 – 力扣（LeetCode）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例

输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

思考

不同之处在于 backtracking的时候不用i+1

这是因为本题的元素是可以重复读取的。(注意和77 组合， 216组合总和III的区别)

back_tracking(candidates, target, i);

40 组合总和II

40. 组合总和 II – 力扣（LeetCode）

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

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

注意：解集不能包含重复的组合。

示例

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
]

思路

这道题目和39.组合总和如下区别：

1. 本题candidates 中的每个数字在每个组合中只能使用一次。
2. 本题数组candidates的元素是有重复的，而39.组合总和 是无重复元素的数组candidates

最后本题和39.组合总和 要求一样，解集不能包含重复的组合。

本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

按carl哥所说，定义两个新名词：树层去重和树枝去重。

• 树层去重：需要对数组排序，值相同的元素不允许重用
• 树枝去重：不允许重复使用同一个元素

// 要对同一树层使用过的值相同的元素进行跳过
if (i > startIndex && candidates[i] == candidates[i - 1]) {continue;}

以及，本题和39的区别还有一点：本题candidates中的每个数字在每个组合中只能使用一次

back_tracking(candidates, target, i + 1); /* need i + 1 */

代码

class Solution {
private:
int sum;
vector<vector<int>> res;
vector<int> path;
public:
    void back_tracking(vector<int>& candidates, int target, int index) {
        if (sum == target) {
            res.push_back(path);
            return ;
        }

        for (int i = index; i < candidates.size() && sum + candidates[i] <= target; i++) {
            if (i > index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum += candidates[i];
            path.push_back(candidates[i]);
            back_tracking(candidates, target, i + 1);
            sum -= candidates[i];
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        back_tracking(candidates, target, 0);
        return res;
    }
};

切割经典题目

131 分割回文串

131. 分割回文串 – 力扣（LeetCode）

给你一个字符串 s，请你将s分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例

输入：s = “aab” 输出：[[“a”,”a”,”b”],[“aa”,”b”]]

思路

典型的“切割问题”

1. 观察示例输入 aab，candidate中存在重复的元素
2. 观察示例输出[“a”,”a”,”b”],此处与组合问题不同，允许同值存在。

那么我们需要截取子串，并判断子串是否是回文串：

string str = s.substr(startIndex, i - startIndex + 1);
if (isPalindrome(str)) {
    /* ... */
}

切割过后的位置不能重复切割，所以回溯时我们使用i+1;

backTracking(s, i + 1);

代码

class Solution {
private:
    vector<vector<string>> res;
    vector<string> path;
public:
    bool isPalindrome(const string &s) {
        int start = 0;
        int end = s.length();
        for (int i = start, j = end - 1; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    void backTracking(const string &s, int startIndex) {
        if (startIndex >= s.size()) {
            res.push_back(path);
            return ;
        }

        for (int i = startIndex; i < s.size(); i++) {
            string str = s.substr(startIndex, i - startIndex + 1);
            if (isPalindrome(str)) {
                path.push_back(str);
            } else {
                continue ;
            }

            backTracking(s, i + 1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        return res;
    }
};

93 复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例

输入：s = “25525511135” 输出：[“255.255.11.135″,”255.255.111.35”]

思考

依然是“切割问题”

1. 退出条件：有3个pointNum
2. 需要坚持每一段的ip合法性
   1. 若以0开头，后不能跟数字
   2. 要是0~255
3. 使用s.insert和s.erase增减pointnum

代码

class Solution {
private:
    vector<string> result;
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) {
            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)) {
                s.insert(s.begin() + i + 1 , '.');
                pointNum++;
                backtracking(s, i + 2, pointNum);
                pointNum--;
                s.erase(s.begin() + i + 1);
            } else break;
        }
    }
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) {
                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) {
                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;
    }
};

子集理论

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。

什么时候for可以从0开始呢？

求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续会讲到的。

子集经典题目

78 子集

78. 子集 – 力扣（LeetCode）

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的

子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例

输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

思考

和组合的区别在于组合是叶子节点是我们想要的答案，而排列是所有节点都是我们想要的答案。那么显而易见，只需要将非叶子节点也加入即可。

故而结果集的加入以及递归的退出条件如下：

        res.push_back(path);
        if (path.size() == nums.size()) {
            return ;
        }

代码

class Solution {
    vector<vector<int>> res;
    vector<int> path;
public:
    void back_tracking(vector<int>& nums, int startIndex) {
        res.push_back(path);
        if (path.size() == nums.size()) {
            return ;
        }

        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            back_tracking(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        back_tracking(nums, 0);
        return res;
    }
};

90 子集II

90. 子集 II – 力扣（LeetCode）

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的

子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例

输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

思考

树层去重，需要排序

代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void back_tracking(vector<int>& nums, int startIndex) {
        res.push_back(path);
        if (startIndex == nums.size()) {
            return ;
        }

        unordered_set<int> set;
        for (int i = startIndex; i < nums.size(); i++) {
            if (set.find(nums[i]) != set.end()) {
                continue;
            }

            set.insert(nums[i]);
            path.push_back(nums[i]);
            back_tracking(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        back_tracking(nums, 0);
        return res;
    }
};

491 递增子序列

491. 非递减子序列 – 力扣（LeetCode）

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例

输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

思考

在经过 子集 的解决后，我们已经可以找出子集了。本题需要递增子序列，也就是说

1. 需要对原数据进行一轮排序
2. 在写入res的时候要判断path中的个数>=2

尝试做了以上两点后，验证测试用例，发现结果如下:

输入

nums =

[4,6,7,7]

输出

[[4,6],[4,6,7],[4,6,7,7],[4,6,7],[4,7],[4,7,7],[4,7],[6,7],[6,7,7],[6,7],[7,7]]

预期结果

[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

这是由于输入用例中存在有不同的元素，但是元素的值是一样的，这就需要进行树层剪枝，同一个父节点下值相同的元素不需要重复使用。

这我们可以使用一个set记录，将同一层下使用过的数据值加入这个set，在后续使用时若能在set中find到这个值，则跳过这个值。

以及，经过实验，原数据是不需要排序的。。否则每一个结果都是符合递增子序列的要求了。

故而在元素入path的时候我们需要判断下当前入队的元素和上一个元素，若当前入队的小于上一个，则跳过。

所以，关键在于：

for ...
    if ((!path.empty() && nums[i] < path.back()) || set.find(nums[i]) != set.end()) {
        continue;
    }

以上的代码包含了

1. 递增比较的逻辑
2. 单层去重的逻辑

代码

#define MIN_RES_SIZE 2

class Solution {
    vector<vector<int>> res;
    vector<int> path;
public:
    void back_tracking(vector<int> &nums, int startIndex) {
        if (path.size() >= MIN_RES_SIZE) {
            res.push_back(path);
        }

        if (path.size() == nums.size()) {
            return ;
        }

        unordered_set<int> set;
        for (int i = startIndex; i < nums.size(); i++) {
            if ((!path.empty() && nums[i] < path.back()) || set.find(nums[i]) != set.end()) {
                continue;
            }

            set.insert(nums[i]);
            path.push_back(nums[i]);
            back_tracking(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        back_tracking(nums, 0);
        return res;
    }
};

排列经典题目

46 全排列

46. 全排列 – 力扣（LeetCode）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思考

从示例中我们可以看到，与组合不同，对于排列来说{1,2}和{2,1}是两个不同的结果。所以排列没必要使用startIndex了。对于每条树枝来说，可以使用一个used数组记录已选择/未选择的节点。

代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void back_track(vector<int> &nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return ;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) {
                continue;
            }

            used[i] = true;
            path.push_back(nums[i]);
            back_track(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        back_track(nums, used);
        return res;
    }
};