首页Coding

# LeetCode 131. 分割回文串

131. Palindrome Partitioning

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

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

示例 1：

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

示例 2：

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

提示：

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

# 思路

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

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

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

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

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

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

# Method: 回溯

算法思路：

  1. 确定递归函数的参数

    • string s ：原始的字符串
    • int startIndex ：待分割字符串的起始位置

  2. 递归的终止条件： startIndex 到达字符串 s 的尾后，字符串 s 已分割完成，当前递归结束

  3. 单层搜索的逻辑

    • 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]={True,若 i≥j(f[i+1][j−1])∧(s[i]==s[j]),若 i<jf[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)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≤0 \le  digits.length  ≤4\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(3m×4n)O(3^m \times 4^n)，其中，mm 是输入到  digits  中的、对应键盘上有三个字母的数字个数（包括数字 2、3、4、5、6、8），nn 是对应四个字母的数字个数（包括数字 7、9），m+nm + n 是输入数字的总个数，对应的字母组合一共有 3m×4n3^m \times 4^n 种


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


参考：



# LeetCode 22. 括号生成


22. Generate Parentheses


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


示例 1：


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



示例 2：


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



提示：


    

  • 1≤n≤81 \le n \le 8
    • 



# Method: 回溯


算法思路：


回溯函数的参数：


    

  • vector<string>& ans  ：存放所有可行的组合
    • 

  • string path  ：当前遍历的组合
    • 

  • int open  ：当前组合中的左括号数量
    • 

  • int close  ：当前组合中的右括号数量
    • 

  • int n  ：限定的括号对数
    • 



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


单层递归的逻辑：


    

  • 若左括号数量小于 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×2n)O(n \times 2^n)，其中，nn 为字符串的长度


    

  • 一个长为 nn 的字符串最多可能有 2n2^n 个子序列，遍历所有子序列需 O(2n)O(2^n) 时间
    • 

  • 每个子序列可能都需要进行一次合法性检测，需 O(n)O(n) 时间
    • 



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


    

  • 递归调用栈的最大深度为 O(n)O(n)
    • 

  • 每次递归调用时都需要复制一次字符串 str，所需空间为 O(n)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≤1 \le  candidates.length  ≤30\le 30
    • 

  • 1≤1 \le  candidates[i]  ≤200\le 200
    • 

  • candidates  的所有元素互不相同
    • 

  • 1≤1 \le  target  ≤500\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≤1 \le  candidates.length  ≤100\le 100
    • 

  • 1≤1 \le  candidates[i]  ≤50\le 50
    • 

  • 1≤1 \le  target  ≤30\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≤2 \le  k  ≤9\le 9
    • 

  • 1≤1 \le  n  ≤60\le 60
    • 



# 思路


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


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




# Method: 回溯


算法思路：


    

  1. 

    定义三个全局变量
    

      

    • vector<vector<int>> result  ：所有可行路径
      • 

    • vector<int> path  ：当前路径
      • 

    • int sum  ：当前路径和
      • 

    

    2. 

  2. 

    确定回溯函数的参数
    

      

    • int k  ：目标子集的大小
      • 

    • int n  ：目标和
      • 

    • int startIndex  ：递归函数体中的  for  循环遍历起始位置
      • 

    

    3. 

  3. 

    回溯的终止条件：已经选取  k  个元素，即， path.size() == k
    

    4. 

  4. 

    单层搜索过程
    

      

    • 若已经选取  k  个元素，进一步判断当前路径和  sum  是否等于目标和  n

        

      • 若是，记录当前路径，结束当前递归
        • 

      • 若否，直接结束当前递归
        • 

      

      • 

    • 若未选取  k  个元素，利用  for  循环遍历  startIndex  至  9  之间的数，针对其中每个数，执行以下操作：

        

      • 更新当前路径以及路径和：将  i  加入到路径  path  中，并计算  sum = sum + i
        • 

      • 继续查找下一个数：递归到下一个数，即， backtracking(k, n, i + 1)
        • 

      • 回溯：回退路径  path.pop_back  ，回退路径和  sum = sum - i
        • 

      

      • 

    

    5. 



代码实现：


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(C9k×k)O(C_9^k \times k)，一共有 O(C9k)O(C_9^k) 种组合（从 99 个数中选出 kk 个数），每种组合进行递归判断的时间代价为 O(k)O(k)


空间复杂度：O(k)O(k)，其中， path  数组所需空间、递归使用的栈空间均为 O(k)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≤1 \le  nums.length  ≤6\le 6
    • 

  • −10≤-10 \le  nums[i]  ≤10\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×n!)O(n \times n!)，其中 nn 是数组  nums  的长度


    

  • 一共有 O(n!)O(n!) 种全排列
    • 

  • 每一种排列方案填入  result  数组都需要 O(n)O(n) 的时间
    • 



空间复杂度：O(n)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≤1 \le  nums.length  ≤8\le 8
    • 

  • −10≤-10 \le  nums[i]  ≤10\le 10
    • 



# 思路


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


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


# Method: 回溯 + 排序


# 算法思想


    

  1. 

    先对  nums  数组进行排序，使得重复元素在  nums  数组中连续
    

    2. 

  2. 

    在递归函数中的去重操作：
    

      

    • 若  nums[i]  在上层递归中被选取过，本层不再选取  nums[i]
      • 

    • 若  nums[i] == nums[i - 1]  （  i > 0  ），并且  nums[i - 1]  在上层递归中未被选取，则本层递归会选取  nums[i - 1]  ，故而本层不再选取  nums[i]
      • 

    

    3. 



若使用  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≤1 \le  nums.length  ≤15\le 15
    • 

  • −100≤-100 \le  nums[i]  ≤100\le 100
    • 



# 思路


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


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


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


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


    

  • 由于需要对每一层递归的  for  循环遍历进行去重，每一层都需要定义一个数组来实现哈希表（本题的  nums[i]  取值范围较小，可直接用数组实现哈希法）
    • 

  • 特别地，每一层递归中的哈希数组仅作用于当前层，不影响其他层，故而下一层可以使用上一层已经选择过的、数组  nums  中的重复元素
    • 



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


# Method: 回溯 + 哈希


算法思路：


    

  1. 

    在使用数组  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. 

  2. 

    本题要求递增子序列长度至少为 2 ，因此，在将序列加入到结果集前需要检验序列的长度
    

    3. 



代码实现：


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≤1 \le  n  ≤20\le 20
    • 

  • 1≤1 \le  k  ≤n\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: 回溯


算法思路：


    

  1. 

    确定回溯函数的参数与返回值
    

      

    • 参数：元素的取值范围  n  ，选取元素的个数  k  ，当前递归选择元素的起点  startIndex

        

      • 每次从集合中选取元素，可选择的范围都会收缩， startIndex  就是用来记录选取元素的起始位置
        • 

      

      • 

    • 回溯算法一般不需要返回值，返回类型为  void
      • 

    

    2. 

  2. 

    回溯函数的终止条件： path  数组大小等于  k  ，说明已经找到  k  个数的组合，记录当前结果即可返回
    

    3. 

  3. 

    回溯函数的单层搜索过程
    

      

    • for  循环每次从  startIndex  开始遍历

        

      • 记遍历的元素为  i
        • 

      • 处理节点：将  i  放入  path  数组中（记录递归的路径）
        • 

      • 递归到树的下一层：为子集选择下一个元素（注意，下一层搜索要从  i + 1  开始）
        • 

      • 回溯：因为需要遍历这一层的其他子树，故而将  i  从  path  从取出
        • 

      

      • 

    

    4. 





这里定义了  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(Cnk×k)O(C_n^k \times k)，一共有 CnkC_n^k 种组合方案（从 nn 个数中选出 kk 个数），其中每一种组合方案填入  result  数组都需要 O(k)O(k) 的时间


空间复杂度：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≤1 \le  nums.length  ≤10\le 10
    • 

  • −10≤-10 \le  nums[i]  ≤10\le 10
    • 

  • nums  中的所有元素 互不相同
    • 



# 思路


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


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




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


参考：代码随想录：子集


# Method: 回溯


算法思路：


    

  1. 

    递归函数的参数
    

      

    • vector<int> nums  ：原始数组
      • 

    • vector<vector<int>> &result  ：存放所有的子集
      • 

    • vector<int> path  ：当前的子集
      • 

    • int index  ： for  循环遍历起点
      • 

    

    2. 

  2. 

    递归终止条件：剩余集合为空（即，到达叶节点， index == nums.size()  ），递归结束
    

    3. 

  3. 

    单层搜索的逻辑： for  循环遍历  nums  数组元素  nums[i] （从索引  index  开始遍历）：
    

      

    • 更新子集：将元素  nums[i]  添加到子集  path  中
      • 

    • 存储结果：将子集  path  添加到结果数组  result  中
      • 

    • 递归到下一层：继续扩充  path  这一子集（下一层递归的  for  循环从  i + 1  开始遍历）
      • 

    • 回溯：撤销本次  for  循环对  path  的更改
      • 

    

    4. 



特别地，由于空集也是数组  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(2n×n)O(2^n \times n)，其中 nn 是数组  nums  的长度


    

  • 一共有 O(2n)O(2^n) 个子集
    • 

  • 构造每个子集的时间代价为 O(n)O(n)
    • 



空间复杂度：O(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 = <!--swig0-->; // 四个方向
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(MN×3L)O(M N \times 3^L) ，其中，MM 和 NN 分别为网格 grid 的行数和列数，LL 是字符串 word 的长度


    

  • 在  exist  函数内，需要遍历每一个出发位置，时间复杂度为 O(MN)O(M N)
    • 

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



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


    

  • visited 数组所需空间为 O(MN)O(M N)
    • 

  • 对于每一个出发位置 (i, j) ，递归所需的栈空间为 O(min⁡(L,MN))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≤1 \le  nums.length  ≤10\le 10
    • 

  • −10≤-10 \le  nums[i]  ≤10\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≤1 \le  s.length  ≤20\le 20
    • 

  • s  consists of digits only.
    • 



# 思路


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


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


    

  • 子串以 '0' 开头，且子串长度大于 1 （即，对应的整数有先导 0）
    • 

  • 子串有非数字字符（本题的  s  只含有数字字符，无需考虑这一情况）
    • 

  • 子串对应的整数大于 255
    • 



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


# Method: 回溯


算法思路：


    

  1. 

    递归函数的参数
    

      

    • vector<string> &result  ：存放所有可行的分割方案（即，所有有效的 IP 地址）
      • 

    • string path  ：当前的分割方案
      • 

    • int startIndex  ：当前递归层的分割起始位置
      • 

    • int pointNum  ：此前已添加的逗点数量
      • 

    

    2. 

  2. 

    递归终止条件：如果已经添加了 3 个逗点（即， pointNum == 3  ），说明已经将字符串分成了四段，分割完成，递归结束
    

      

    • 结束递归前，需要判断当前分割方案是否合法（更准确地说，需要判断第四个整数是否合法，因为前面三个整数在之前的递归层中已经判断过），若当前分割方案合法，则需将其加入到结果集  result  之中
      • 

    

    3. 

  3. 

    单层搜索的逻辑：利用  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  循环继续遍历
      • 

    

    4. 



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


    

  • 可以在分割字符串  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 地址