【递归与回溯深度解析：经典题解精讲（上篇）】—— LeetCode

【递归与回溯深度解析：经典题解精讲（上篇）】—— LeetCode

全排列

解题思路 这是一道典型的 回溯（Backtracking）问题，我们需要枚举所有可能的子集。关键点是每个数字都有两种选择：要么包含，要么不包含。

详细步骤：

• 回溯的核心思想： 每个元素都有两种选择：加入当前子集或者不加入。 通过递归，处理完每个元素后生成对应的子集。
• 终止条件： 如果当前遍历的索引等于数组长度，说明已经生成一个完整的子集，将其加入结果。
• 回溯的过程： 将当前元素加入子集，继续递归。 回溯后，将当前元素移除，继续探索不加入当前元素的可能性

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    // 存储最终结果的二维数组，每个子数组是一个排列
    vector<vector<int>> ret;
    // 当前递归路径，用于构建一个排列
    vector<int> path;
    // 标记数组，用于记录 nums 中的元素是否被使用过
    bool check[7]; // 假设 nums.size() 最大为 7，实际可用动态数组优化

public:
    vector<vector<int>> permute(vector<int>& nums) 
    {
        // 开始深度优先搜索
        dfs(nums);

        return ret;
    }

    // 深度优先搜索函数
    void dfs(vector<int>& nums)
    {
        // 如果当前路径的长度等于 nums 的大小，表示形成了一个完整排列
        if(nums.size() == path.size())
        {
            // 将当前路径加入最终结果
            ret.push_back(path);
            return;
        }

        // 遍历 nums 中的每个元素
        for(int i = 0; i < nums.size(); i++)
        {
            // 如果当前元素未被使用
            if(!check[i])
            {
                // 将当前元素加入路径
                path.push_back(nums[i]);

                // 标记该元素为已使用
                check[i] = true;

                // 递归处理下一个位置
                dfs(nums);

                // 回溯：撤销选择
                path.pop_back();

                // 解除标记，表示该元素可以再次使用
                check[i] = false;
            }
        }
    }
};

子集

解题思路 这是一个典型的 回溯+交换（Backtracking with swapping）问题。关键点是枚举数组的所有排列组合。为了实现全排列，每次递归时需要将一个数字固定到当前位置，然后递归处理剩余数字。

详细步骤：

• 回溯的核心思想： 固定当前的一个数字，通过递归处理剩余数字。 通过交换，动态调整数组，避免额外空间开销。
• 终止条件： 如果当前索引达到数组长度，说明已经生成一个完整排列，将其加入结果。
• 回溯的过程： 将当前索引位置的数字与后续数字交换，递归处理剩余数字。 回溯时恢复数组原状（撤销交换）。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    // `ret` 用于存储所有子集的结果
    vector<vector<int>> ret; 
    // `path` 用于存储当前递归路径上的子集
    vector<int> path;
public:
    // 主函数，用于计算输入数组的所有子集
    vector<vector<int>> subsets(vector<int>& nums)
    {
        // 从第 0 个元素开始深度优先搜索
        dfs(nums, 0);    
        // 返回最终生成的所有子集
        return ret;
    }

    // 深度优先搜索函数，`nums` 为输入数组，`pos` 为当前元素的位置索引
    void dfs(vector<int>& nums, int pos)
    {
        // 递归结束条件：如果已经遍历到数组末尾，将当前路径加入结果
        if (nums.size() == pos)
        {
            ret.push_back(path); // 将当前路径（一个子集）添加到结果集中
            return; // 终止当前递归
        }

        // 选择当前元素：将当前元素加入路径
        path.push_back(nums[pos]);
        // 递归处理包含当前元素的子集
        dfs(nums, pos + 1);
        // 回溯：移除最后加入的元素，恢复路径状态
        path.pop_back();

        // 不选择当前元素：直接递归处理不包含当前元素的子集
        dfs(nums, pos + 1);
    }
};

出所有子集的异或总和再求和

解题思路 这是一道典型的 回溯 问题，要求计算所有子集的异或值总和。

子集枚举：通过回溯枚举所有子集。 异或计算：在回溯的过程中，用一个变量记录当前路径的异或值。 终止条件：当遍历到数组末尾时，将当前异或值累加到结果中。 详细步骤：

• 使用回溯生成所有子集，定义一个变量记录当前子集的异或总和。

在回溯时，每次有两种选择：

• 选择当前元素：更新异或值并递归。 不选择当前元素：保持当前状态递归。

遍历完后，将路径上的异或值加入结果中。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    // 用于记录当前路径中的 XOR 结果
    int path;
    // 用于记录所有子集的 XOR 结果的总和
    int sum;

public:
    int subsetXORSum(vector<int>& nums) 
    {
        // 从 0 开始的深度优先搜索 (DFS)
        dfs(nums, 0);

        // 返回累加的 XOR 和
        return sum;    
    }

    // 深度优先搜索函数，用于生成所有子集并计算 XOR
    void dfs(vector<int>& nums, int pos)
    {
        // 每次进入递归时，将当前路径的 XOR 结果加入总和
        sum += path;

        // 从当前位置开始，尝试添加下一个数字
        for(int i = pos; i < nums.size(); i++)
        {
            // 将当前数字加入路径（通过 XOR 操作）
            path ^= nums[i];

            // 递归调用，处理当前位置之后的数字
            dfs(nums, i + 1);

            // 撤销选择，恢复路径到上一个状态
            path ^= nums[i];
        }
    }
};

全排列||

解题思路 这是一道 回溯+剪枝 问题，核心在于生成全排列的同时避免重复。

关键点：

• 排序去重： 为了避免重复，先将数组排序。 在递归时，当遇到相同的元素且上一个相同的元素还未使用完时，跳过该分支。
• 状态数组： 使用一个 check数组记录当前元素是否被使用，防止重复选取。
• 回溯过程： 在路径中加入当前数字，递归处理剩余数字。 回溯时移除当前数字。

代码语言：javascript代码运行次数：0运行复制

class Solution
{
    vector<vector<int>> ret;  // 用于存储所有不重复的排列结果
    vector<int> path;         // 当前排列的路径
    bool check[9];            // 用于标记某个元素是否已被使用（假设输入数组最多有 9 个元素）
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        // 对输入数组进行排序，这是为了处理重复元素，方便去重
        sort(nums.begin(),());
        dfs(nums, 0); // 从第 0 个位置开始深度优先搜索
        return ret;   // 返回所有不重复排列的结果
    }

    void dfs(vector<int>& nums, int pos)
    {
        // 如果路径的长度等于数组大小，说明到一个完整的排列
        if (pos == nums.size())
        {
            ret.push_back(path); // 将当前排列加入结果集
            return;              // 结束当前递归
        }

        // 遍历数组中的每个元素
        for (int i = 0; i < nums.size(); i++)
        {
            // 如果当前元素未被使用
            // 并且以下任一条件成立：
            // 1. 当前是第一个元素 (i == 0)
            // 2. 当前元素与前一个元素不同 (nums[i] != nums[i - 1])
            // . 当前元素等于前一个元素，但前一个元素已被使用 (check[i - 1] == true)
            if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1]))
            {
                path.push_back(nums[i]); // 将当前元素加入路径
                check[i] = true;         // 标记当前元素已被使用
                dfs(nums, pos + 1);      // 递归处理下一个位置
                path.pop_back();         // 回溯：移除最后一个元素
                check[i] = false;        // 回溯：取消当前元素的使用标记
            }
        }
    }
};

电话号码的字母组合

解题思路 这是一个 回溯问题，核心在于处理多分支递归。每个数字可以映射到多个字母，相当于在路径中枚举每个数字对应的字母。

详细步骤：

• 建立映射表： 使用哈希表记录数字到字母的映射关系。
• 回溯搜索： 每次递归处理一个数字，遍历其对应的所有字母。 将当前字母加入路径，递归处理剩余数字。 回溯时移除当前字母。
• 终止条件： 如果路径长度等于输入字符串长度，生成一个完整的字母组合。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    string path;                  // 用于存储当前的组合路径
    vector<string> ret;           // 存储所有可能的字母组合结果
    string hash[10] = {"", "",    // 映射 0 和 1 对应无字母
                       "abc",     // 映射数字 2 到对应的字母
                       "def",     // 映射数字 
                       "ghi",     // 映射数字 4
                       "jkl",     // 映射数字 5
                       "mno",     // 映射数字 6
                       "pqrs",    // 映射数字 7
                       "tuv",     // 映射数字 8
                       "wxyz"};   // 映射数字 9
public:
    vector<string> letterCombinati(string digits) 
    {
        // 如果输入的数字字符串为空，直接返回空的结果集
        if(digits.size() == 0) return ret;
        
        // 从第 0 个数字开始进行深度优先搜索 (DFS)
        dfs(digits, 0);
        
        // 返回所有可能的字母组合
        return ret;
    }

    void dfs(string& digits, int pos)
    {
        // 如果当前的路径长度等于输入的数字长度，说明已生成一个完整的字母组合
        if(pos == digits.size())
        {
            ret.push_back(path); // 将当前路径加入结果集
            return;             // 结束当前递归
        }
        
        // 遍历当前数字对应的所有字母
        for(auto ch : hash[digits[pos] - '0'])
        {
            path.push_back(ch);  // 将当前字母加入路径
            dfs(digits, pos + 1); // 递归处理下一个数字
            path.pop_back();     // 回溯：移除最后一个字母
        }
    }
};

括号生成

解题思路 这是一个 回溯问题，关键在于如何保证括号的合法性。

详细步骤：

• 规则约束： 只有在左括号数量未超过 n 时，才可以加入左括号。 只有在右括号数量小于左括号数量时，才可以加入右括号。
• 递归过程： 每次递归处理一个括号，根据约束条件选择加入左括号或右括号。
• 终止条件： 当左右括号数量都等于 n 时，生成一个完整的括号组合。

代码语言：javascript代码运行次数：0运行复制

class Solution 
{
    int left, right, n;          // `left`表示当前已经使用的左括号数量，`right`表示已使用的右括号数量，`n`表示总的括号对数
    vector<string> ret;          // 存储所有可能的合法括号组合结果
    string path;                 // 当前生成的括号路径
public:
    vector<string> generateParenthesis(int _n) 
    {
        n = _n;                  // 初始化括号对数
        dfs();                   // 开始深度优先搜索
        return ret;              // 返回所有合法的括号组合
    }

    void dfs()
    {
        // 如果右括号数量等于括号对数，说明当前路径是一个完整的合法括号组合
        if(right == n)
        {
            ret.push_back(path); // 将当前路径加入结果集
            return;              // 结束当前递归
        }

        // 如果左括号数量小于总括号对数，可以继续添加左括号
        if(left < n)
        {
            path.push_back('('); // 添加一个左括号
            left++;              // 左括号计数加一
            dfs();               // 递归处理下一个状态
            path.pop_back();     // 回溯：移除最后一个括号
            left--;              // 回溯：左括号计数减一
        }

        // 如果右括号数量小于左括号数量，可以继续添加右括号
        if(right < left)
        {
            path.push_back(')'); // 添加一个右括号
            right++;             // 右括号计数加一
            dfs();               // 递归处理下一个状态
            path.pop_back();     // 回溯：移除最后一个括号
            right--;             // 回溯：右括号计数减一
        }
    }
};

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-01-17，如有侵权请联系 cloudcommunity@tencent 删除前往查看数组搜索leetcode遍历递归