力扣hot100--＞递归/回溯

目录

递归/回溯

1. 17. 电话号码的字母组合

2. 22. 括号生成

3. 39. 组合总和

4. 46. 全排列

 5. 78. 子集

递归/回溯

1. 17. 电话号码的字母组合

中等

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

// 定义一个类 Solution
class Solution {
public:
    // 定义一个字符串向量 v，存储数字到字母的映射关系，数字 2 到 9 分别对应不同的字母组合
    vector<string> v{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    // 定义一个字符串向量 result，用于存储所有可能的字母组合结果
    vector<string> result;
    
    // 定义一个字符串 path，用于记录当前组合的路径
    string path;

    // 递归函数 recursive，用于生成所有可能的字母组合
    void recursive(string digits, int index) {
        // 递归结束条件：当 path 的长度等于输入的数字串长度时，将当前组合添加到结果中
        if (path.size() == digits.size()) {
            result.push_back(path);
            return;
        }

        // 根据当前数字获取对应的字母字符串
        string s = v[digits[index] - '0'];

        // 遍历当前数字对应的每个字母
        for (int i = 0; i < s.size(); ++i) {
            // 将当前字母添加到 path
            path.push_back(s[i]);

            // 递归调用，下一个数字
            recursive(digits, index + 1);

            // 回溯：移除最后一个添加的字母，以便尝试下一个字母组合
            path.pop_back();
        }
    }

    // 主函数 letterCombinations，调用递归函数并返回结果
    vector<string> letterCombinations(string digits) {
        // 如果输入为空，返回空的结果集
        if (digits.size() == 0) return {};
        
        // 调用递归函数，开始生成字母组合
        recursive(digits, 0);

        // 返回所有生成的字母组合
        return result;
    }
};
 

2. 22. 括号生成

中等

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

class Solution {
public:
    vector<string> ans;  // 存储所有有效的括号组合
    string cur;          // 当前构建的括号组合字符串

    // 回溯函数
    void backtrack(string& cur, int open, int close, int n) {
        // 基线条件：当当前组合的长度等于 2*n 时，意味着已生成一个有效的括号组合
        if (cur.size() == 2 * n) {
            ans.push_back(cur);  // 将当前组合添加到结果中
            return;              // 返回，结束当前递归
        }

        // 1. 尝试添加左括号
        if (open < n) {  // 只有在左括号数量小于 n 时才能添加左括号
            cur.push_back('(');  // 将左括号添加到当前组合
            backtrack(cur, open + 1, close, n);  // 递归调用，更新 open 数量
            cur.pop_back();  // 回溯：移除最后一个字符，尝试其他组合
        }

        // 2. 尝试添加右括号
        if (close < open) {  // 只有在右括号数量小于左括号数量时才能添加右括号
            cur.push_back(')');  // 将右括号添加到当前组合
            backtrack(cur, open, close + 1, n);  // 递归调用，更新 close 数量
            cur.pop_back();  // 回溯：移除最后一个字符，尝试其他组合
        }
    }

    // 生成 n 对括号的主函数
    vector<string> generateParenthesis(int n) {
        backtrack(cur, 0, 0, n);  // 初始调用，open 和 close 都为 0
        return ans;  // 返回所有生成的有效括号组合
    }
};

 解释：

• 条件 if (close < open) 确保右括号的数量不会超过左括号的数量，从而保持组合的有效性。

3. 39. 组合总和

中等

给你一个 无重复元素 的整数数组 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 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

class Solution {
public:
    // 用于存储所有符合条件的组合
    vector<vector<int>> result;
    // 用于存储当前的组合路径
    vector<int> path;

    // 递归+回溯函数
    // candidates: 数组中的可选数字
    // target: 目标和
    // sum: 当前路径的和
    // index: 当前选择开始的索引位置
    void backTracking(vector<int>& candidates, int target, int sum, int index) {
        // 如果当前和已经超过目标值，结束该路径
        if(sum > target){
            return;
        }

        // 如果找到一个符合条件的组合
        if(target == sum){
            result.push_back(path);  // 将当前路径加入结果集中
            return;
        }

        // 遍历候选数组，从 index 开始
        for(int i = index; i < candidates.size(); ++i) {
            // 将当前选择加入路径和 sum 中
            sum += candidates[i];
            path.push_back(candidates[i]);

            // 递归调用自身，传入i而不是index或index+1，以允许重复使用相同的元素
            backTracking(candidates, target, sum, i);

            // 回溯，撤销当前选择
            sum -= candidates[i];
            path.pop_back();
        }
    }

    // 主函数，用于调用回溯函数并返回结果
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backTracking(candidates, target, 0, 0); // 初始化 sum 为 0，从索引 0 开始
        return result;  // 返回符合条件的所有组合
    }
};

 解释：

关于for循环中int=index而不是i=0问题：

考虑一个具体的例子，假设我们有以下输入：

candidates = [2, 3, 6, 7] target = 7

1. 使用 index 控制

当 index 传入 0，第一次迭代将会是：

• 第一个元素 2（index = 0）
  • 选择 2，接下来可以再次选择 2 或选择 3（因为 i 从 0 开始）。你将得到 [2, 2, 3] 这种组合。
• 第二个元素 3（index = 1）
  • 当递归调用回来后，当前元素 2 被弹出，index 继续向前推进。
  • 选择 3 时，i 从 1 开始，因此可以选择 [3, 4]，形成组合 [3, 4]。

这个方法避免了相同元素在同一层级的选择，比如 2 被重复选择。

2. 使用 0 开始的情况

如果 for 循环从 0 开始：

• 第一个元素 2（i = 0）
  • 选择 2，然后 backTracking(candidates, target, sum, 0) 再次递归调用，允许再次选择 2。
• 第二个元素 2 再次选择（i = 0）
  • 你将得到路径 [2, 2, 2]，但也会通过选择 2、然后 2、然后 3 再生成组合。

造成的后果

通过从 0 开始，每一层递归都允许选择之前已经被选中的元素，导致生成的组合可能重复。例如 [2, 2, 3] 和 [2, 3, 2] 被认为是不同的组合，但实际上它们是相同的组合。

总结

• index 变量的设计：允许算法在递归过程中控制哪些元素可以被选择，同时避免在同一递归层级重复选择已经在路径中的元素。
• 从 0 开始的后果：如果每次递归都从 0 开始，可能会产生重复组合，并增加计算的复杂度。

4. 46. 全排列

中等

给定一个不含重复数字的数组 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 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

class Solution {
public:
    // 存储所有的排列结果
    vector<vector<int>> result;
    // 存储当前排列的路径
    vector<int> path;

    // 回溯函数
    void backTracking(vector<int>& nums, vector<bool>& used) {
        // 终止条件：当前路径的长度等于数组的长度，表示形成了一个完整排列
        if (nums.size() == path.size()) {
            result.push_back(path);  // 将当前排列加入结果集
            return;
        }

        // 遍历所有元素，尝试每种可能
        for (int i = 0; i < nums.size(); ++i) {
            // 如果该元素已经使用过，则跳过
            if (used[i]) continue;

            // 标记当前元素为已使用
            used[i] = true;
            path.push_back(nums[i]);  // 将元素加入当前排列路径
            
            // 递归调用自身，继续生成排列
            backTracking(nums, used);

            // 回溯，撤销当前选择，准备尝试其他排列
            path.pop_back();
            used[i] = false;
        }
    }

    // 主函数，返回所有的排列
    vector<vector<int>> permute(vector<int>& nums) {
        // 初始化标记数组，长度和 nums 一致，初始值为 false
        vector<bool> used(nums.size(), false);
        
        // 开始回溯
        backTracking(nums, used);
        return result;
    }
};

5. 78. 子集

中等

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

class Solution {
public:
    vector<vector<int>> result; // 用于存储所有子集的结果
    vector<int> path; // 当前的子集路径

    void backtrack(vector<int>& nums, int index) {
        // 结束条件：当 index 等于数组大小时返回
        if (index == nums.size()) {
            return;
        }

        // 将当前子集加入结果中
        result.push_back(path);

        // 遍历剩余的元素，生成子集
        for (int i = index; i < nums.size(); ++i) {
            path.push_back(nums[i]); // 选择当前元素
            backtrack(nums, i + 1); // 递归调用，选择下一个元素
            path.pop_back(); // 回溯，撤销选择
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums, 0); // 从索引 0 开始
        return result; // 返回结果
    }
};