# LeetCode 131. 分割回文串

131. Palindrome Partitioning

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

回文串是正着读和反着读都一样的字符串。

示例 1：

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

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

$1 \le$ s.length $\le 16$
s 仅由小写英文字母组成

# 思路

分割问题本质上与组合问题类似，例如字符串 "aaba"

组合问题：选取一个 "a" 之后，再在 "aba" 中选取第二个，依此类推
分割问题：分割第一段的 "a" 之后，再在 "aba" 中分割第二段，依此类推

因此，分割问题也可以抽象成一棵树

其中， for 循环用于遍历分割线的位置，递归用于将分割线后面的字符做进一步的分割

根据题中对回文串的定义可知，回文串应为左右对称的字符串，可通过双指针法（定义左、右指针）来判断字符串是否左右对称

参考：代码随想录：分割回文串

# Method: 回溯

算法思路：

确定递归函数的参数
- string s ：原始的字符串
- int startIndex ：待分割字符串的起始位置
递归的终止条件： startIndex 到达字符串 s 的尾后，字符串 s 已分割完成，当前递归结束
单层搜索的逻辑
- for 循环，遍历分割线的位置 i （也就相当于遍历不同的分割方案）
  - 起始位置至分割线之间的字符，即，索引为 [startIndex, i] 的字符，就是当前分割所得的子串，记作 str
  - 判断 str 是否为回文串：若不是回文串，则说明当前分割不可行，需跳过当前分割方案；若是回文串，则进行下一步操作
  - 将回文串 str 保存到 path （分割所得回文串的集合）当中
  - 递归到下一层，继续分割索引为 [i + 1, s.size() - 1] 的字符
  - 回溯，弹出本次已经填在 path 中的子串 str ，以便遍历其余分割方案

代码实现：

vector<vector<string>> result;  // 存放所有的分割方案
vector<string> path;            // 存放当前已经分割的回文子串

bool isPalindrome(string str) { // 判断 str 是否为回文串
    if (str.size() == 0) return true;
    for (int l = 0, r = str.size() - 1; l < r; l++, r--) { // 双指针
        if (str[l] != str[r]) return false;
    }
    return true;
}

void backTracking(string s, int startIndex) { // 将以 startIndex 为起始索引的子串进行分割
    if (startIndex == s.size()) { // 分割的起始位置在 s 尾后，说明分割已完成
        result.push_back(path);   // 存储当前的分割方案
        return;
    }
    for (int i = startIndex; i < s.size(); i++) { // 对分割线的位置进行遍历
        // 获取 s 中索引为 [startIndex, i] 的子串
        string str(s.begin() + startIndex, s.begin() + i + 1);
        if (!isPalindrome(str)) continue; // 分割得到的子串不是回文串，跳过当前分割方案
        path.push_back(str);    // 子串是回文串，将其放入 path
        backTracking(s, i + 1); // 递归到下一层，分割字符串 s 中的后续字符
        path.pop_back();        // 回溯，删除已存储的字符串 str
    }
}

vector<vector<string>> partition(string s) {
    backTracking(s, 0);
    return result;
}

其中， string str(s.begin() + startIndex, s.begin() + i + 1); 等效于 string str = s.substr(startIndex, i - startIndex + 1);

# 优化

上述算法利用了双指针法判断字符串是否为回文串，这会带来重复计算

以分割 "aaba" 为例

如果第一次分割子串 "a" ，剩余子串为 "aba" ，则第二次分割需要分别判断 "a" "ab" "aba" 是否为回文串。进一步地，如果第二次分割的子串为 "a" ，则剩余子串为 "ba" ，第三次分割需要分别判断 "b" "ba" 是否为回文串
如果第一次分割子串为 "ab" ，剩余子串为 "ba" ，第二次分割需要分别判断 "b" "ba" 是否为回文串
因此，子串 "b" 与 "ba" 被重复判断过

对此，可以先将字符串 s 中的每个子串进行预处理（判断其是否为回文串），可采用的办法包括：动态规划、记忆化搜索，具体可见力扣官方题解：分割回文串

这里采用动态规划方法进行预处理：

f[i][j] 表示索引 [i, j] 之间字符组成的子串是否为回文串
状态转移方程：
$f[i][j] = \begin{cases} True, \textrm{若} \ i \ge j \\ (f[i + 1][j - 1]) \land (s[i] == s[j]), \textrm{若} \ i < j \end{cases}$
其中， $\land$ 表示逻辑与，即，索引 [i, j] 的子串为回文串，有以下三种情况：
- 该子串为空
- 该子串长度为 1（即 i == j ）
- 首尾字符相同（即 s[i] == s[j] ）并且索引 [i + 1, j - 1] 子串为回文串

由此，只需 $O(1)$ 的时间就能判断任意子串为回文串

代码实现：

vector<vector<string>> result;
vector<string> path;

vector<vector<int>> f; // 动态规划的结果

void backTracking(string s, int startIndex) {
    if (startIndex == s.size()) {
        result.push_back(path);
        return;
    }
    for (int i = startIndex; i < s.size(); i++) {
        if (!f[startIndex][i]) continue; // 字符串 s[startIndex, i] 不是回文串
        string str(s.begin() + startIndex, s.begin() + i + 1);
        path.push_back(str);
        backTracking(s, i + 1);
        path.pop_back();
    }
}

vector<vector<string>> partition(string s) {
    f.assign(s.size(), vector<int>(s.size(), true)); // 初始化 f ：值全为 true
    for (int i = s.size() - 1; i >= 0; i--) {        // 计算索引为 [i, j] 的子串是否为回文串
        for (int j = i + 1; j < s.size(); j++) {
            f[i][j] = (s[i] == s[j]) && (f[i + 1][j - 1]); // 状态转移
        }
    }
    backTracking(s, 0);
    return result;
}

# LeetCode 17. 电话号码的字母组合

LeetCode 17. Letter Combinations of a Phone Number

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意，1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

$0 \le$ digits.length $\le 4$
digits[i] is a digit in the range ['2', '9'] .

# 思路

本题每一个数字代表的是不同集合，也就是求不同集合之间的组合

首先，需要建立键盘数字与字符串之间的映射，这里使用字符串数组将数字 0 - 9 与字母对应起来

const string letterMap[10] = {
    "",     // 数字 0
    "",     // 数字 1
    "abc",  // 数字 2
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"  // 数字 9
}

本题可通过回溯算法解题

递归函数内嵌一个 for 循环， for 循环用于遍历数字所对应的字母（即，遍历 letterMap ）
递归用于实现对数字的遍历（即，遍历 digits ）

# Method: 回溯

算法思路： for 循环横向遍历，递归纵向遍历，回溯不断调整结果集

本题输入的 digits[i] 是范围 [2, 9] 之间的数字，因此不需要考虑 0 和 1 这样的特殊情况

代码实现：

const string letterMap[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

vector<string> result;
string path;

void backtracking(string digits, int index) {
    if (path.size() == digits.size()) {
        result.push_back(path);
        return;
    }
    int num = digits[index] - '0';   // 当前遍历到的数字（index 指向的数字）
    string letters = letterMap[num]; // 当前数字对应的字符串
    for (int i = 0; i < letters.size(); i++) { // for 循环：遍历 letterMap[num] 字符串
        path.push_back(letters[i]);      // 处理节点
        backtracking(digits, index + 1); // 递归到下一层：选取第 index + 1 位数字对应的字母
        path.pop_back();                 // 回溯
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.size() == 0) return result; // 处理 digits 为空这一特殊情况
    backtracking(digits, 0);
    return result;
}

须注意： digits 是 string 型的对象，对应的元素 digits[index] 是 char 型，需先将 char 型转换成 int 型才能索引字符串数组 letterMap

时间复杂度： $O(3^m \times 4^n)$ ，其中， $m$ 是输入到 digits 中的、对应键盘上有三个字母的数字个数（包括数字 2、3、4、5、6、8）， $n$ 是对应四个字母的数字个数（包括数字 7、9）， $m + n$ 是输入数字的总个数，对应的字母组合一共有 $3^m \times 4^n$ 种

空间复杂度： $O(m + n)$ ，递归调用的层数为 $m + n$

参考：

代码随想录
力扣官方题解

# LeetCode 22. 括号生成

22. Generate Parentheses

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

$1 \le n \le 8$

# Method: 回溯

算法思路：

回溯函数的参数：

vector<string>& ans ：存放所有可行的组合
string path ：当前遍历的组合
int open ：当前组合中的左括号数量
int close ：当前组合中的右括号数量
int n ：限定的括号对数

终止条件：括号总数量为 $2 n$ ，即，已经有 $n$ 对括号时，将当前组合添加到目标数组，当前递归结束

单层递归的逻辑：

若左括号数量小于 n ，则可添加左括号，并递归到下一层
若右括号数量小于左括号数量，则可添加右括号，并递归到下一层

代码实现：

void backTracking(vector<string>& ans, string path, int open, int close, int n) {
    if (path.size() == n * 2) {
        ans.push_back(path);
        return;
    }
    if (open < n) {     // 添加左括号
        path.push_back('(');
        backTracking(ans, path, open + 1, close, n);
        path.pop_back();
    }
    if (close < open) { // 添加右括号
        path.push_back(')');
        backTracking(ans, path, open, close + 1, n);
        path.pop_back();
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> ans;
    backTracking(ans, "", 0, 0, n);
    return ans;
}

# LeetCode 301. 删除无效的括号

301. Remove Invalid Parentheses

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

1 $\le$ s.length $\le$ 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号

# Method: 回溯

算法思路：

首先利用括号匹配的规则来计算最少需要删除的左括号数量 lremove 和右括号数量 rremove，即，遍历字符串 s：

当遇到左括号时：llremove 加 1
当遇到右括号时：
- 若 llremove 为 0，该右括号无法匹配，故而 rremove 加 1
- 若 llremove 不为 0，该右括号可以与之前的左括号匹配，故而 llremove 减 1

然后利用回溯算法遍历所有可能的删除非法括号的方案

回溯函数的参数：字符串 string str，删除括号的起点 int start，所需删除的左括号数量 llremove，所需删除的右括号数量 rremove
回溯的终止条件：llremove 与 rremove 同时为 0，无需再删除括号，当前递归结束（在返回之前需要先调用 isValid 函数来检查当前字符串是否合法匹配，若合法匹配则将其记录下来）
单层搜索过程：遍历字符串 str 的位置 i
- 如果 i != start 且 str [i] == str [i - 1]，说明在这一层递归中遇到了连续相同的括号，此时我们不需要再重复搜索，故而跳过当前的 i，以此实现去重（比如当前遇到的字符串为 "(((())"，去掉前四个左括号中的任意一个，生成的字符串是一样的）
- 如果剩余字符串长度小于 lremove + rremove，当前的方案必然无法得到合法匹配的括号，因此，当前递归结束
- 如果 lremove 大于 0 且 str [i] 为左括号，可将当前左括号删除，然后递归到下一层（由于需要删除位置 i 的左括号，递归到下一层的字符串 str 应为 str.substr (0, i) + str.substr (i + 1)，并且起始位置 start 应为 i，lremove 应为 lremove - 1）
- 如果 rremove 大于 0 且 str [i] 为右括号，可将当前右括号删除，然后递归到下一层

其中，isValid 函数可按如下方式实现：

定义 count 作为非法的左括号数量
遍历字符串 str
- 若遇到左括号，count 加 1
- 若遇到右括号
  - 如果 count 等于 0，当前右括号无法匹配，返回 false
  - 如果 count 不为 0，当前右括号可以匹配，count 减 1
判断 count 是否为 0，若为 0 则返回 true，否则返回 false

可考虑将 “计算 lremove、rremove” 与 “isValid 函数” 定义成一个可供复用的新函数

代码实现：（本代码使用的是可复用的函数 check，函数返回 {0, 0} 时表示字符串合法）

vector<string> res;
vector<string> removeInvalidParentheses(string s) {
    vector<int> remove(2, 0);
    remove = check(s); // 计算需移除的左括号数量和右括号数量
    helper(s, 0, remove[0], remove[1]);
    return res;
}

void helper(string str, int start, int lremove, int rremove) {
    if (lremove == 0 && rremove == 0) { // 已达到需要删除的最小括号数量
        vector<int> tmp(2, 0);
        tmp = check(str);               // 检查字符串内的括号是否完全匹配
        if (tmp[0] == 0 && tmp[1] == 0) // 字符串内的括号完全匹配
            res.push_back(str);         // 记录当前方案
        return;
    }
    for (int i = start; i < str.size(); ++i) {
        if (i > start && str[i] == str[i - 1]) continue; // 去重（连续相同的括号只需搜索一次）
        if (lremove + rremove > str.size() - i) return;  // 剪枝（剩余的字符数小于需删除的括号数）
        if (lremove > 0 && str[i] == '(')                // 尝试删除一个左括号
            helper(str.substr(0, i) + str.substr(i + 1), i, lremove - 1, rremove);
        if (rremove > 0 && str[i] == ')')                // 尝试删除一个左括号
            helper(str.substr(0, i) + str.substr(i + 1), i, lremove, rremove - 1);
    }
}

vector<int> check(string& s) {
    int lremove = 0; // 需移除的左括号数量（最小数量）
    int rremove = 0; // 需移除的右括号数量（最小数量）
    for (auto c : s) {
        if (c == '(') ++lremove;         // 左括号加一
        else if (c == ')') {
            if (lremove == 0) ++rremove; // 右括号与左括号不匹配
            else --lremove;              // 右括号与左括号匹配
        }
    }
    return {lremove, rremove};
}

时间复杂度： $O(n \times 2^n)$ ，其中， $n$ 为字符串的长度

一个长为 $n$ 的字符串最多可能有 $2^n$ 个子序列，遍历所有子序列需 $O(2^n)$ 时间
每个子序列可能都需要进行一次合法性检测，需 $O(n)$ 时间

空间复杂度： $O(n^2)$ ，不考虑返回数组所需空间

递归调用栈的最大深度为 $O(n)$
每次递归调用时都需要复制一次字符串 str，所需空间为 $O(n)$

参考：leetcode-solution

# LeetCode 39. 组合总和

39. Combination Sum

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

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

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

示例 1：

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

示例 2：

输入：candidates = [2,3,5], target = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入：candidates = [2], target = 1
输出：[]

提示：

$1 \le$ candidates.length $\le 30$
$1 \le$ candidates[i] $\le 200$
candidates 的所有元素互不相同
$1 \le$ target $\le 500$

# Method: 回溯

注意本题 candidates 中的元素可以被无限制重复选取，下一层递归中的 for 循环遍历起点应与当前层相同

本题对子集的元素数量并没有要求，因此递归返回的条件应为：元素和大于等于目标和

搜索过程如下所示：

代码实现：

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++) {
        path.push_back(candidates[i]);
        sum += candidates[i];
        backTracking(candidates, target, sum, i); // 元素可重复选取，下一层从 i 开始
        path.pop_back();
        sum -= candidates[i];
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    backTracking(candidates, target, 0, 0);
    return result;
}

# 优化（剪枝）

可以先对 candidates 进行排序（元素按升序排列）

在递归过程中，如果当前层的 sum + candidates[i] （即，下一层的 sum ）已经大于 target ，无需再针对当前 candidates[i] 进行下一层的递归，也无需再继续遍历当前层的 candidates 数组（即，无需再进行 for 循环的遍历）

代码实现：

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> candidates, int target, int sum, int startIndex) {
    if (sum == target) { // 注意这里无需处理 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(candidates, target, sum, i);
        path.pop_back();
        sum -= candidates[i];
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end()); // 排序，以便剪枝
    backTracking(candidates, target, 0, 0);
    return result;
}

参考：代码随想录

# LeetCode 40. 组合总和 II

40. Combination Sum II

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

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

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

示例 1：

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

示例 2：

输入：candidates = [2,5,2,1,2], target = 5
输出：
[
[1,2,2],
[5]
]

提示：

$1 \le$ candidates.length $\le 100$
$1 \le$ candidates[i] $\le 50$
$1 \le$ target $\le 30$

# 思路

本题与 LeetCode 39. 组合总和 有较大不同，本题的 candidates 数组包含重复元素，且每个元素只能在子集中出现一次（重复元素可以分别出现一次）

对此，递归下一层时需要从 i + 1 开始 for 循环的遍历，以使得每个元素最多只使用一次（重复的元素可以分别使用一次）

但是，如果仅仅是这样的话，结果将会产生重复的组合，以示例 1 为例，结果为 [[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]] ，可以发现 [1,2,5],[1,7] 这两个重复出现了，此时回溯搜索的第一层如下所示：

可以发现，在当前的递归层中，由于 candidates 数组含有重复元素， for 循环进行横向遍历时会取出重复元素（误当成不同的子树），产生重复的子集 [1,2,5,6,7,10] ，最终导致 [1,2,5],[1,7] 在答案中出现两次

---> B1[2,5,6,7,10]
B [1,2,5,6,7,10] -- 取 2
---> B2[1,5,6,7,10]
B [1,2,5,6,7,10] -- 取 5
---> B3[1,2,6,7,10]
B [1,2,5,6,7,10] -- 取 6
---> B4[1,2,5,7,10]
B [1,2,5,6,7,10] -- 取 7
---> B5[1,2,5,6,10]
B [1,2,5,6,7,10] -- 取 10
---> B6[1,2,5,6,7]
```

因此，还需要对同一层的 for 循环进行去重，避免在同一层递归中取出重复元素

# Method: 回溯

有以下两种方法可以用来去重

# 排序

可直接利用 for 循环的起点 index 来实现当前层的去重

首先须对 candidates 进行排序，使得重复元素的出现是连续的
在 for 循环遍历 i 的过程中，如果发现 i > index 且 candidates[i] == candidates[i - 1] ，则说明 candidates[i] 这个元素已经处理过了，不能再重复处理，因此，跳过当前 i

类似于 LeetCode 39. 组合总和 ，可对回溯搜索进行剪枝优化

代码实现：

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> candidates, int target, int sum, int index) {
    if (sum == target) {
        result.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; // 同一层的去重
        path.push_back(candidates[i]);
        sum += candidates[i];
        backTracking(candidates, target, sum, i + 1); // 不含重复元素，下一层从 i + 1 开始遍历
        path.pop_back();
        sum -= candidates[i];
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end()); // 排序，以实现 去重 以及 剪枝
    backTracking(candidates, target, 0, 0);
    return result;
}

注意：条件 i > index 不能改成 i > 0 ，因为当前层的 for 循环是从 index 开始遍历的，只需判断在当前层是否处理过元素 candidates[i] ，而不需要判断上一层是否处理过元素 candidates[i]

if (i > index && candidates[i] == candidates[i - 1]) continue; 跳过的是同一层的重复元素
if (i > 0 && candidates[i] == candidates[i - 1]) continue; 不仅会跳过同一层递归里的重复元素，也会跳过不同层次递归的重复元素（即，上一层处理过元素 candidates[index - 1] ，下一层将不能够处理重复元素 candidates[index] ）。在此情况下，针对示例 1 得到的结果为 [[1,2,5],[1,7],[2,6]] ，缺失了 [1,1,6] 这一组合

---> B[1,2,5,6,7,10]
B [1,2,5,6,7,10] -. 不会再取 1 .- B1 [2,5,6,7,10]
B [1,2,5,6,7,10] -- 取 2
---> B2[1,5,6,7,10]
B [1,2,5,6,7,10] -- 取 5
---> B3[1,2,6,7,10]
B [1,2,5,6,7,10] -- 取 6
---> B4[1,2,5,7,10]
B [1,2,5,6,7,10] -- 取 7
---> B5[1,2,5,6,10]
B [1,2,5,6,7,10] -- 取 10
---> B6[1,2,5,6,7]
```

参考：代码随想录：组合总和 II

# 哈希 + 排序

在每一层定义一个哈希表，用来记录 for 循环处理过的元素

这里使用排序是为了剪枝，并不是为了去重

代码实现：

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> candidates, int target, int sum, int index) {
    if (sum == target) {
        result.push_back(path);
        return;
    }
    unordered_set<int> uset; // 用于记录当前层的 for 循环遍历情况
    for (int i = index; i < candidates.size() && sum + candidates[i] <= target; i++) { // sum + candidates[i] <= target 用以剪枝
        if (uset.find(candidates[i]) != uset.end()) continue; // 同一层的去重
        uset.insert(candidates[i]);
        path.push_back(candidates[i]);
        sum += candidates[i];
        backTracking(candidates, target, sum, i + 1);
        path.pop_back();
        sum -= candidates[i];
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end()); // 排序，便于剪枝
    backTracking(candidates, target, 0, 0);
    return result;
}

使用哈希 unordered_set 去重的效率较低（时间复杂度和空间复杂度都比较高）

参考：代码随想录

# LeetCode 216. 组合总和 III

LeetCode 216. Combination Sum III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字 1 到 9
每个数字 最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1：

输入：k = 3, n = 7
输出：[[1,2,4]]

示例 2：

输入：k = 3, n = 9
输出：[[1,2,6],[1,3,5],[2,3,4]]

示例 3：

输入：k = 4, n = 1
输出：[]
解释：不存在有效的组合

提示：

$2 \le$ k $\le 9$
$1 \le$ n $\le 60$

# 思路

类似于 LeetCode 77. 组合，旨在查找满足条件的子集，只不过本题多出了一个条件，即， k 个数的和须为 n

因此，需记录递归的路径和，并将递归的终止条件修改为：元素个数等于 k 且路径和等于 n

# Method: 回溯

算法思路：

定义三个全局变量
- vector<vector<int>> result ：所有可行路径
- vector<int> path ：当前路径
- int sum ：当前路径和
确定回溯函数的参数
- int k ：目标子集的大小
- int n ：目标和
- int startIndex ：递归函数体中的 for 循环遍历起始位置
回溯的终止条件：已经选取 k 个元素，即， path.size() == k
单层搜索过程
- 若已经选取 k 个元素，进一步判断当前路径和 sum 是否等于目标和 n
  - 若是，记录当前路径，结束当前递归
  - 若否，直接结束当前递归
- 若未选取 k 个元素，利用 for 循环遍历 startIndex 至 9 之间的数，针对其中每个数，执行以下操作：
  - 更新当前路径以及路径和：将 i 加入到路径 path 中，并计算 sum = sum + i
  - 继续查找下一个数：递归到下一个数，即， backtracking(k, n, i + 1)
  - 回溯：回退路径 path.pop_back ，回退路径和 sum = sum - i

代码实现：

vector<vector<int>> result; // 所有可行路径
vector<int> path; // 当前路径
int sum = 0; // 当前路径的和

void backtracking(int k, int n, int startIndex) {
    if (path.size() == k) {
        if (sum == n) result.push_back(path); // 满足条件，将路径添加到目标数组
        return; // path.size() == k 但sum != n 时，直接返回
    }
    for (int i = startIndex; i <= 9; i++) { // 横向遍历
        path.push_back(i); // 更新路径
        sum += i;          // 更新路径和
        backtracking(k, n, i + 1); // 递归到下一层，查找下一个数
        path.pop_back();   // 回溯
        sum -= i;          // 回溯
    }
}

vector<vector<int>> combinationSum3(int k, int n) {
    backtracking(k, n, 1);
    return result;
}

# 优化（剪枝）

针对上述算法，可进行以下两个方面的剪枝：

若当前路径和大于 n ，不需要再向下查找（继续查找也无法找到可行解），直接结束当前递归
若可供选择的剩余元素个数（ 9 - i + 1 ）小于仍需选择的元素个数（ k - path.size() ），也不需要再继续向下查找

代码实现

vector<vector<int>> result;
vector<int> path;
int sum = 0;

void backtracking(int k, int n, int startIndex) {
    if (sum > n) return; // 剪枝
    if (path.size() == k) {
        if (sum == n) result.push_back(path);
        return;
    }
    for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
        path.push_back(i);
        sum += i;
        backtracking(k, n, i + 1);
        path.pop_back();
        sum -= i;
    }
}

vector<vector<int>> combinationSum3(int k, int n) {
    backtracking(k, n, 1);
    return result;
}

时间复杂度： $O(C_9^k \times k)$ ，一共有 $O(C_9^k)$ 种组合（从 $9$ 个数中选出 $k$ 个数），每种组合进行递归判断的时间代价为 $O(k)$

空间复杂度： $O(k)$ ，其中， path 数组所需空间、递归使用的栈空间均为 $O(k)$

参考：代码随想录

# LeetCode 46. 全排列

46. Permutations

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

$1 \le$ nums.length $\le 6$
$-10 \le$ nums[i] $\le 10$
nums 中的所有整数互不相同

# 思路

本题要求的是数组的全排列，需要区分元素在集合中的先后顺序，即， [1, 2] 与 [2, 1] 是不同的排列

若将该问题抽象成树结构，则需记录所有叶节点

因为数组中所有元素都需要处理一次，对应树结构上的叶节点
需要获取所有可能的排列方式，故而需要遍历所有叶节点

此前的组合问题、分割问题、子集问题不考虑集合中元素的顺序，即，不管按照什么顺序来选取元素，只要元素组成的集合相同，得到的结果就是相同的

我们之前采用的选取顺序是：从递归的上层到下层，元素是按照索引逐渐增大的顺序选取的（例如，当前层选择第 i 位元素，下一层只能选择第 i 位以后的元素）
此时，对于每一层递归而言，“上层已经访问过的元素” 与 “ 尚未访问过的元素 ” 之间具有明确的分界线，故而可以使用 startIndex 来标记 for 循环遍历的起点
具体可见 LeetCode 77. 组合

但是在排列问题中，从递归的上层到下层，元素并不全都按照索引递增顺序选取（这是因为，选择元素的先后顺序不同，会得到不同的排列），此时，“上层已经访问过的元素” 与 “ 尚未访问过的元素 ” 之间不存在分界线，因此不能再使用 startIndex 了

对此，可以引入 used 数组（或者是哈希表）来标记上层已经选取的元素，需注意，递归函数中的 for 循环要从 0 开始

# Method: 回溯 + 哈希

代码实现：

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> &nums, vector<int> &used) {
    if (path.size() == nums.size()) { // 得到一个全排列，将其添加到结果集
        result.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[nums[i] + 10] == 1) continue; // nums[i] 在之前层次已经使用过
        used[nums[i] + 10] = 1;   // 当前层次使用了 nums[i] ，更新标记
        path.push_back(nums[i]);  // 将 nums[i] 添加到 path
        backTracking(nums, used); // 递归到下一层
        used[nums[i] + 10] = 0;   // 回溯：撤销对 nums[i] 的标记
        path.pop_back();          // 回溯：撤销对 path 的更改
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<int> used(21, 0);  // nums[i] 的取值范围为 [-10, 10]
    backTracking(nums, used);
    return result;
}

时间复杂度： $O(n \times n!)$ ，其中 $n$ 是数组 nums 的长度

一共有 $O(n!)$ 种全排列
每一种排列方案填入 result 数组都需要 $O(n)$ 的时间

空间复杂度： $O(n)$ ，这里考虑了递归使用的栈空间，递归的深度为 $O(n)$

这里用 used[nums[i] + 10] 来表示 nums[i] 是否被使用过，其实也可以直接用 used[i] 的值来表示 nums 数组的第 i 位是否被使用过

# LeetCode 47. 排列 II

47. Permutations II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有 不重复 的全排列。

示例 1：

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

示例 2：

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

提示：

$1 \le$ nums.length $\le 8$
$-10 \le$ nums[i] $\le 10$

# 思路

本题在 LeetCode 46. 全排列 的基础上，为 nums 数组引入了重复元素，要求返回所有不重复的全排列

因此，需要在每一层递归中，对 for 循环所遍历的元素进行去重

# Method: 回溯 + 排序

# 算法思想

先对 nums 数组进行排序，使得重复元素在 nums 数组中连续
在递归函数中的去重操作：
- 若 nums[i] 在上层递归中被选取过，本层不再选取 nums[i]
- 若 nums[i] == nums[i - 1] （ i > 0 ），并且 nums[i - 1] 在上层递归中未被选取，则本层递归会选取 nums[i - 1] ，故而本层不再选取 nums[i]

若使用 used[i] 值为 1 来表示 nums[i] 已经被上层递归选取，则元素去重的代码如下

for (int i = 0; i < num.size(); i++) {
    if (used[i] == 1) continue; // 情况一
    if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue; // 情况二
    // 选取 nums[i] 的相关操作
}

# 代码实现

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> nums, vector<int> used) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i] == 1) continue; // 上层递归已经选取过 nums[i]
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)
            continue; // 上一层未选取 nums[i - 1] ，但是当前层会选取 nums[i - 1] ，故而无需选取 nums[i]
        path.push_back(nums[i]);    // 更新 path 数组
        used[i] = 1;                // 更新 used 数组
        backTracking(nums, used);   // 递归到下一层
        used[i] = 0;                // 回溯：撤销对 used 数组的更改
        path.pop_back();            // 回溯：撤销对 path 数组的更改
    }
}

vector<vector<int>> permuteUnique(vector<int> &nums) {
    sort(nums.begin(), nums.end());  // 排序，以便去重
    vector<int> used(nums.size(), 0);
    backTracking(nums, used);
    return result;
}

代码随想录：全排列 II 上提到， if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 1) continue 也可以实现同一层递归中不选取重复元素，只不过效率相对较低

事实上，这里用到的 used 数组也是哈希法的一种实现

# 回溯 + 哈希

# 算法思想

在每一层定义一个哈希表，用来记录 for 循环处理过的元素

# 代码实现

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> nums, vector<int> used) {
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    unordered_set<int> uset;        // 用于记录当前层 for 循环遍历情况
    for (int i = 0; i < nums.size(); i++) {
        if (used[i] == 1) continue; // 上层递归已经选取过 nums[i]
        if (uset.find(nums[i]) != uset.end()) continue; // 本层递归已经处理过 nums[i] 的重复元素
        uset.insert(nums[i]);       // 记录元素
        path.push_back(nums[i]);
        used[i] = 1;
        backTracking(nums, used);
        used[i] = 0;
        path.pop_back();
    }
}

vector<vector<int>> permuteUnique(vector<int> &nums) {
    vector<int> used(nums.size(), 0);
    backTracking(nums, used);
    return result;
}

这里同时使用了 used 数组和哈希表 unordered_set ，前者用于实现不同层次递归间的去重，后者用于单次递归中 for 循环的去重

注：使用哈希 unordered_set 去重的效率较低（时间复杂度和空间复杂度都比较高）

# LeetCode 491. 递增子序列

491. Increasing Subsequences

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

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

示例 1：

输入：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]]

示例 2：

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

提示：

$1 \le$ nums.length $\le 15$
$-100 \le$ nums[i] $\le 100$

# 思路

本题属于子集问题，需要记录所有可行的子集。即，如果将该问题抽象成一棵树，则需要记录树上所有满足条件的节点

类似于 LeetCode 90. 子集 II ，本题的 nums 数组也同样含有重复元素，因此，不能在同一层递归中取出重复元素（但可以分别在不同层次的递归中取出重复元素），即，需要对 for 循环的横向遍历进行去重

然而，不同于 LeetCode 90. 子集 II ，本题需要的是子序列，元素之间的相对位置关系不能更改，因此不能对数组 nums 进行排序。故而不能再采用 LeetCode 90. 子集 II 中的去重方式

对此，可以采用哈希法来去重

由于需要对每一层递归的 for 循环遍历进行去重，每一层都需要定义一个数组来实现哈希表（本题的 nums[i] 取值范围较小，可直接用数组实现哈希法）
特别地，每一层递归中的哈希数组仅作用于当前层，不影响其他层，故而下一层可以使用上一层已经选择过的、数组 nums 中的重复元素

此外，题目要求每个子序列都是递增的，因此，在把元素放入子集前，还需要比较该元素与子集中的最后一个元素进行比较

# Method: 回溯 + 哈希

算法思路：

在使用数组 used 实现哈希表时，由于 nums[i] 的取值范围为 [-100, 100] ，我们可以将 nums[i] 映射到 used 数组中索引为 nums[i] + 100 的位置。即
- 若 used[nums[i] + 100] == 1 ，本层递归已经选过 nums[i] 这个数，不再重复选择
- 若 used[nums[i] + 100] == 0 ，本层递归没有选过 nums[i] 这个数，可以考虑选择 nums[i] （因为还需要判断其是否能够构成新的递增序列）
本题要求递增子序列长度至少为 2 ，因此，在将序列加入到结果集前需要检验序列的长度

代码实现：

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> nums, int index) {
    if (path.size() > 1) {       // 需要记录所有的递增子序列（子序列中至少要有两个元素）
        result.push_back(path);
        // 注意，这里不能加 return ，因为要遍历树上所有节点
    }
    vector<int> used(201, 0);    // 用于标记 nums[i] 这个数是否已经操作过
    for (int i = index; i < nums.size(); i++) {
        if (!path.empty() && nums[i] < path.back() || used[nums[i] + 100] == 1)
            continue;            // 非递增，或者，当前递归层已经操作过 nums[i] 这个数
        path.push_back(nums[i]);
        used[nums[i] + 100] = 1; // nums[i] 被选择，更新标记
        backTracking(nums, i + 1);
        path.pop_back();
    }
}

vector<vector<int>> findSubsequences(vector<int> &nums) {
    backTracking(nums, 0);
    return result;
}

注意，在定义 used 数组时，需要初始化：大小为 201 ，每个元素值为 0

参考：代码随想录：递增子序列

# LeetCode 77. 组合

77. Combinations

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

$1 \le$ n $\le 20$
$1 \le$ k $\le n$

# 思路

针对示例 n = 4, k = 2 ，可通过以下代码来实现暴力搜索

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

但如果要解决 n 为 100 ，k 为 50 的情况，暴力搜索的写法需要嵌套 50 层 for 循环

此时，可以用递归来解决嵌套层数的问题，即，每一次的递归中嵌套一个 for 循环

这里可以把问题抽象为如下树形结构，回溯法的搜索过程就是这样一个树型结构的遍历过程， for 循环用来横向遍历，递归用来纵向遍历。其中，每搜索到一个叶节点，就是找到一个可行结果

可以发现， n 相当于树的宽度， k 相当于树的高度

# Method: 回溯

算法思路：

确定回溯函数的参数与返回值
- 参数：元素的取值范围 n ，选取元素的个数 k ，当前递归选择元素的起点 startIndex
  - 每次从集合中选取元素，可选择的范围都会收缩， startIndex 就是用来记录选取元素的起始位置
- 回溯算法一般不需要返回值，返回类型为 void
回溯函数的终止条件： path 数组大小等于 k ，说明已经找到 k 个数的组合，记录当前结果即可返回
回溯函数的单层搜索过程
- for 循环每次从 startIndex 开始遍历
  - 记遍历的元素为 i
  - 处理节点：将 i 放入 path 数组中（记录递归的路径）
  - 递归到树的下一层：为子集选择下一个元素（注意，下一层搜索要从 i + 1 开始）
  - 回溯：因为需要遍历这一层的其他子树，故而将 i 从 path 从取出

这里定义了 vector<vector<int>> result 和 vector<int> path 两个全局变量，分别存放所有可行的搜索结果、当前的搜索结果（递归的路径）。事实上，可以把这两个变量定义到递归函数的参数里，这里定义为全局变量有两方面的考虑：1) 函数参数过多时会影响可读性；2) 定义成全局变量可显式地表现出回溯的过程

代码实现：

vector<vector<int>> result; // 存放所有符合条件的搜索结果
vector<int> path;           // 当前的搜索结果

void DFS(int n, int k, int startIndex) {
    if (path.size() == k) { // 子集的大小为 k ，符合条件
        result.push_back(path); // 将当前搜索结果存入 result 数组
        return;
    }
    for (int i = startIndex; i <= n; i++) { // for 循环：控制树的横向遍历
        path.push_back(i); // 处理节点 
        DFS(n, k, i + 1);  // 递归：控制树的纵向遍历，注意下一层搜索要从 i + 1 开始
        path.pop_back();   // 回溯，撤销处理的节点
    }
}

vector<vector<int>> combine(int n, int k) {
    DFS(n, k, 1);
    return result;
}

# 优化（剪枝）

事实上，当可选择的剩余元素个数小于仍需选择的元素个数时，不再存在可行方案，不需要再进行后续的搜索

换而言之，只有可选择的剩余元素个数大于等于仍需选择的元素个数时，才需进行搜索

因此，可对回溯搜索进行剪枝操作：

当前已选择的元素个数为 path.size() ，后续仍需选择 k - path.size() 个元素
在 i 被选择之前，区间 [i, n] 一共有 n - i + 1 个元素可供选择
因此， for 循环的循环控制条件应为 n - i + 1 >= k - path.size() ，即： i <= n - (k - path.size()) + 1

代码实现：

vector<vector<int>> result;
vector<int> path;

void DFS(int n, int k, int startIndex) {
    if (path.size() == k) {
        result.push_back(path);
        return;
    }
    for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 已剪枝
        path.push_back(i); // 处理节点
        DFS(n, k, i + 1);  // 递归：控制树的纵向遍历，注意下一层搜索要从 i + 1 开始
        path.pop_back();   // 回溯，撤销处理的节点
    }
}

vector<vector<int>> combine(int n, int k) {
    DFS(n, k, 1);
    return result;
}

时间复杂度： $O(C_n^k \times k)$ ，一共有 $C_n^k$ 种组合方案（从 $n$ 个数中选出 $k$ 个数），其中每一种组合方案填入 result 数组都需要 $O(k)$ 的时间

空间复杂度： $O(k)$ ，考虑了递归需要的栈空间以及临时数组 path 所需空间（未考虑存储答案的数组 result ）

参考：

代码随想录
力扣官方题解

# LeetCode 78. 子集

LeetCode 78. Subsets

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

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

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

$1 \le$ nums.length $\le 10$
$-10 \le$ nums[i] $\le 10$
nums 中的所有元素 互不相同

# 思路

组合问题、分割问题、子集问题都可以抽象为一棵树，其中，组合问题和分割问题是在收集树的叶节点，子集问题是收集树的所有节点

因此，可以用回溯搜索法（枚举法）遍历整棵树，并记录所有的节点（每个节点都是一个子集）

注意，子集中的元素是无序的，即，子集 {1, 2} 和子集 {2, 1} 是一样的，因此，每一层递归的 for 循环起始位置不能重复

参考：代码随想录：子集

# Method: 回溯

算法思路：

递归函数的参数
- vector<int> nums ：原始数组
- vector<vector<int>> &result ：存放所有的子集
- vector<int> path ：当前的子集
- int index ： for 循环遍历起点
递归终止条件：剩余集合为空（即，到达叶节点， index == nums.size() ），递归结束
单层搜索的逻辑： for 循环遍历 nums 数组元素 nums[i] （从索引 index 开始遍历）：
- 更新子集：将元素 nums[i] 添加到子集 path 中
- 存储结果：将子集 path 添加到结果数组 result 中
- 递归到下一层：继续扩充 path 这一子集（下一层递归的 for 循环从 i + 1 开始遍历）
- 回溯：撤销本次 for 循环对 path 的更改

特别地，由于空集也是数组 nums 的一个子集，需要将空集 [] 也添加到 result 当中

建议将 vector<int> nums 和 vector<int> path 改为引用传递，即，采用 vector<int> &nums 和 vector<int> &path 形式作为递归函数的参数

代码实现：

void backTracking(vector<int> nums, vector<vector<int>> &result, vector<int> path, int index) {
    if (index == nums.size()) return; // 递归终止条件，这里可以不加这个条件
    for (int i = index; i < nums.size(); i++) {
        path.push_back(nums[i]); // 更新当前子集
        result.push_back(path);  // 将当前子集添加到 result 数组
        backTracking(nums, result, path, i + 1); // 递归到下一层
        path.pop_back();         // 回溯
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    result.push_back(path); // 子集为空集的情况
    backTracking(nums, result, path, 0);
    return result;
}

时间复杂度： $O(2^n \times n)$ ，其中 $n$ 是数组 nums 的长度

一共有 $O(2^n)$ 个子集
构造每个子集的时间代价为 $O(n)$

空间复杂度： $O(n)$ ，这里考虑了递归使用的栈空间，递归的最大深度为 $O(n)$

本题可以将 result.push_back(path); 放到递归函数体的第一行，即，每次递归时都会将子集 path 添加到目标数组 result 中。此时，不需要再单独将空集 [] 添加到目标数组

# LeetCode 79. 单词搜索

79. Word Search

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中 “相邻” 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

# Method: 回溯

算法思路：

遍历 grid 中的每一个位置 (i, j)，判断从该位置出发能否搜索到 word 。特别地，只要找到一个可行的出发点，就说明网格中能够找到 word ，即可返回 true ，否则，说明不能找到，返回 false

为检查从某位置出发能否搜索到 word ，可以定义一个回溯函数：

从 grid 的 (starti, startj) 位置出发，判断能否搜索到字符串 word 的子串 word [startk, word.size () - 1] ，若能够搜索到，则返回 true ，否则，返回 false
其中，每个位置可能向上、下、左、右四个方向移动，因此，在回溯函数体内，需要遍历这四个方向
并且，由于同一个单元格内的字母只允许使用一次，在回溯时需要维护一个 visited 数组，用于标记每个位置是否已经被访问过

代码实现：

vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个方向

bool backTrcking(vector<vector<char>>& board, int starti, int startj, string word, int startk, vector<vector<bool>>& visited) {
    if (board[starti][startj] != word[startk]) return false; // 不匹配，返回 false
    if (startk == word.size() - 1) return true; // startk 已经是 word 的最后一个字符，返回 true
    visited[starti][startj] = true; // 标记 (starti, startj) 位置已访问
    for (auto &dir : directions) {  // 遍历 上 下 左 右 四个方向
        int newi = starti + dir[0]; // 下一个访问位置为 (newi, newj)
        int newj = startj + dir[1];
        if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) { // 位置 (newi, newj) 未越界
            if (visited[newi][newj] == false) { // 未被访问过
                bool flag = backTrcking(board, newi, newj, word, startk + 1, visited); // 递归到下一层
                if (flag) return true; // 从 (newi, newj) 位置出发，能够找到 word[startk + 1] 及其后续字符
            }
        }
    }
    visited[starti][startj] = false;  // 未找到 word ，回溯，撤销对 (starti, startj) 位置的标记
    return false; // 返回 false
}

bool exist(vector<vector<char>>& board, string word) {
    vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) { // 遍历每一个起点 (i, j)，判断能否从该位置出发找到 word
            bool tag = backTrcking(board, i, j, word, 0, visited); // 回溯搜索
            if (tag) return true;
        }
    }
    return false;
}

时间复杂度： $O(M N \times 3^L)$ ，其中， $M$ 和 $N$ 分别为网格 grid 的行数和列数， $L$ 是字符串 word 的长度

在 exist 函数内，需要遍历每一个出发位置，时间复杂度为 $O(M N)$
对于每一个出发位置 (i, j)，需要调用 backTrackinig 回溯函数进行搜索，时间复杂度为 $O(3^L)$ 。这是因为，最多只有第一层递归中的 for 循环有 4 个方向可以搜索，其余每一层递归中的 for 循环最多只能向 3 个方向搜索（即，只能往新位置走，不能往回走）

空间复杂度： $O(M N)$

visited 数组所需空间为 $O(M N)$
对于每一个出发位置 (i, j) ，递归所需的栈空间为 $O(\min(L, MN))$

参考：leetcode-solution

# LeetCode 90. 子集 II

90. Subsets II

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

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

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

$1 \le$ nums.length $\le 10$
$-10 \le$ nums[i] $\le 10$

# 思路

与 LeetCode 78. 子集 相比，本题的 nums 数组含有重复元素，因此，不能在同一层递归中取出重复元素（但可以分别在不同层次的递归中取出重复元素），即，需要对 for 循环的横向遍历进行去重

去重的思路可参考 LeetCode 40. 组合总和 II

# Method: 回溯

针对不同的去重方法，有以下两种实现

# 排序

采用 LeetCode 40. 组合总和 II 中的去重方式

代码实现：

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int> &nums, int index) {
    result.push_back(path);
    for (int i = index; i < nums.size(); i++) {
        if (i > index && nums[i] == nums[i - 1]) continue; // 去重，避免在同一层递归中取出重复元素
        path.push_back(nums[i]);
        backTracking(nums, i + 1);
        path.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end()); // 排序，以便去重
    backTracking(nums, 0);
    return result;
}

这里将 vector<vector<int>> result; 和 vector<int> path; 作为全局变量，实际上也可按照 LeetCode 78. 子集 中的写法，将其作为递归函数的参数（建议采用引用传递的方式传入参数）

# 哈希

思想：在每一层定义一个哈希表，用来记录 for 循环处理过的元素

代码实现：

vector<vector<int>> result;
vector<int> path;

void backTracking(vector<int>& nums, int startIndex) {
    result.push_back(path);
    unordered_set<int> uset; // 用于记录当前层的 for 循环遍历情况
    for (int i = startIndex; i < nums.size(); i++) {
        if (uset.find(nums[i]) != uset.end()) { // 当前层已经处理过 nums[i]
            continue;
        }
        uset.insert(nums[i]);
        path.push_back(nums[i]);
        backTracking(nums, i + 1);
        path.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    backTracking(nums, 0);
    return result;
}

注：使用哈希 unordered_set 去重的效率较低（时间复杂度和空间复杂度都比较高）

参考：代码随想录

# LeetCode 93. 复原 IP 地址

93. Restore IP Addresses

有效 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 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

$1 \le$ s.length $\le 20$
s consists of digits only.

# 思路

本题是一个分割问题（将字符串 s 分割成四个子串），需要列举出所有可行的分割方案

其中，以下情况无法形成有效的 IP 地址

子串以 '0' 开头，且子串长度大于 1 （即，对应的整数有先导 0）
子串有非数字字符（本题的 s 只含有数字字符，无需考虑这一情况）
子串对应的整数大于 255

解题思路类似于 LeetCode 131. 分割回文串

# Method: 回溯

算法思路：

递归函数的参数
- vector<string> &result ：存放所有可行的分割方案（即，所有有效的 IP 地址）
- string path ：当前的分割方案
- int startIndex ：当前递归层的分割起始位置
- int pointNum ：此前已添加的逗点数量
递归终止条件：如果已经添加了 3 个逗点（即， pointNum == 3 ），说明已经将字符串分成了四段，分割完成，递归结束
- 结束递归前，需要判断当前分割方案是否合法（更准确地说，需要判断第四个整数是否合法，因为前面三个整数在之前的递归层中已经判断过），若当前分割方案合法，则需将其加入到结果集 result 之中
单层搜索的逻辑：利用 for 循环遍历分割线的位置 for (int i = startIndex; i < s.size(); i++)
- 截取 [startIndex, i] 这一索引区间内的字符子串，记作 str
- 判断子串 str 是否合法，若不合法，跳过当前分割方案，若合法，继续下一步
- 递归到下一层，以分割后续字符。其中，传入下一层的 path 需在当前 path 的基础上加上 str + '.' ，下一层的分割起始位置 startIndex 需为 i + 1 ，逗点数量 pointNum 需更新为 pointNum + 1 ）
- 回溯：撤销对 path 和 pointNum 的更改，以便 for 循环继续遍历

特别地，针对上述算法可以做以下考虑：

可以在分割字符串 s 前对 s 的长度进行判断，若长度小于 4 ，或者长度大于 12，说明 s 无法形成有效 IP 地址，直接返回空数组即可
子串对应的整数不能大于 255 ，因此，分割的子串长度不能超过 3 ， for 循环遍历分割线位置时无需考虑长度大于 3 的子串

这里将 string path 作为递归函数的参数传入，但采用的是值传递，调用函数时会申请额外的内存空间。为降低空间复杂度，建议采用引用传递，即，将 string path 修改为 string &path

代码实现：

bool isValid(string s, int left, int right) { // 判断 s[left, right] 对应的整数是否有效
    if (s[left] == '0' && right > left) return false; // 整数有先导 0 ，无效
    string str = s.substr(left, right - left + 1);    // 取出索引为 [left, right] 的子串
    int num = 0;
    for (int i = left; i <= right; i++) {             // 将 str 转换为 int 型整数
        num = num * 10 + (s[i] - '0');
        if (num > 255) return false;                  // 整数大于 255 ，无效
    }
    return true;
}

void backTracking(vector<string> &result, string path, string s, int startIndex, int pointNum) {
    if (pointNum == 3) { // 已经添加 3 个逗点，分割结束
        if (startIndex < s.size() && isValid(s, startIndex, s.size() - 1)) { // 判断最后一个整数是否有效
            path += s.substr(startIndex, s.size() - startIndex); // 将最后一个整数放入 path
            result.push_back(path);                              // 将 path 放入结果集
        }
        return;
    }
    for (int i = startIndex; i < s.size() && i <= startIndex + 2; i++) { // 遍历分割线位置，其中，每个整数最多三位
        if (isValid(s, startIndex, i)) { // 判断 s[startIndex, i] 对应整数是否有效
            string str = s.substr(startIndex, i - startIndex + 1);
            backTracking(result, path + str + '.', s, i + 1, pointNum + 1); // 递归到下一层
        }
    }
}

vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    if (s.size() < 4 || s.size() > 12) return result; // IP 地址至少 4 位，至多 12 位
    string path;
    backTracking(result, path, s, 0, 0);
    return result;
}

其中， backTracking(result, path + str + '.', s, i + 1, pointNum + 1); 既实现了递归到一层时的参数更新，也实现了回溯到当前层时的参数回退

参考：代码随想录：复原 IP 地址

回溯

# LeetCode 131. 分割回文串

# 思路

# Method: 回溯

# 优化

# LeetCode 17. 电话号码的字母组合

# 思路

# Method: 回溯

# LeetCode 22. 括号生成

# Method: 回溯

# LeetCode 301. 删除无效的括号

# Method: 回溯

# LeetCode 39. 组合总和

# Method: 回溯

# 优化（剪枝）

# LeetCode 40. 组合总和 II

# 思路

# Method: 回溯

# 排序

# 哈希 + 排序

# LeetCode 216. 组合总和 III

# 思路

# Method: 回溯

# 优化（剪枝）

# LeetCode 46. 全排列

# 思路

# Method: 回溯 + 哈希

# LeetCode 47. 排列 II

# 思路

# Method: 回溯 + 排序

# 算法思想

# 代码实现

# 回溯 + 哈希

# 算法思想

# 代码实现

# LeetCode 491. 递增子序列

# 思路

# Method: 回溯 + 哈希

# LeetCode 77. 组合

# 思路

# Method: 回溯

# 优化（剪枝）

# LeetCode 78. 子集

# 思路

# Method: 回溯

# LeetCode 79. 单词搜索

# Method: 回溯

# LeetCode 90. 子集 II

# 思路

# Method: 回溯

# 排序

# 哈希

# LeetCode 93. 复原 IP 地址

# 思路

# Method: 回溯

回溯

LeetCode - 贪心专题