深度优先搜索与回溯法：全排列及子集问题的决策树与剪枝优化

时间和空间复杂度

1. 时间复杂度

• 每个排列需要遍历 nums 的所有元素，同时需要递归构造排列。
• 全排列的总数为 n!，其中 n 为 nums 的长度。
• 每次构造排列需要 O(n) 的时间复杂度，因此总时间复杂度为：O(n · n!)

2. 空间复杂度

• 递归深度为 O(n)，对应递归栈的最大深度。
• 存储结果的 ret 大小为 O(n · n!)（每个排列长度为 n，共有 n! 个排列）。
• 额外空间为 path 和 check，均为 O(n)。
• 总空间复杂度为：O(n · n!)

二、子集

题目链接：https://leetcode.cn/problems/subsets/description/

解法一：逐位置决策法

核心思想：对于每个位置，都需要明确'选'或者'不选'两种可能，然后继续对后续位置进行递归。

步骤分析

1. 输入数组：nums = [1, 2, 3]。
2. 决策树构造：
   • 对于每个元素，存在两个分支：选它和不选它。
   • 递归过程中，我们先'选'再'回溯'，然后'跳过当前元素'。
3. 递归终止条件：
   • 当递归位置 pos 达到数组末尾（pos == nums.size()）时，将当前路径 path 加入结果集 ret。

运行示例

• 初始调用：dfs(nums, 0)
  • 选 1：path = [1]，递归进入 dfs(nums, 1)
    • 选 2：path = [1, 2]，递归进入 dfs(nums, 2)
      • 选 3：path = [1, 2, 3]，递归终止，保存结果 [[1, 2, 3]]
      • 回溯到选 2 状态：path = [1, 2]
      • 不选 3：path = [1, 2]，递归终止，保存结果 [[1, 2, 3], [1, 2]]
    • 回溯到选 1 状态：path = [1]
    • 不选 2：path = [1]，递归进入 dfs(nums, 2)
      • 选 3：path = [1, 3]，递归终止，保存结果 [[1, 2, 3], [1, 2], [1, 3]]
      • 不选 3：path = [1]，递归终止，保存结果 [[1, 2, 3], [1, 2], [1, 3], [1]]
  • 回溯到初始状态：path = []
  • 不选 1：path = []，递归进入 dfs(nums, 1)
    • 选 2：path = [2]，递归类似上面。
    • 不选 2：path = []，递归继续处理后续。

最终得到所有子集。

代码

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos) {
        if (pos == nums.size()) {
            ret.push_back(path);
            return;
        }
        // 选
        path.push_back(nums[pos]);
        dfs(nums, pos + 1);
        // 回溯 -> 恢复现场
        path.pop_back();
        // 不选
        dfs(nums, pos + 1);
    }
};

解法二：逐元素扩展法

核心思想：直接将当前路径加入结果集，然后从当前位置逐个向后选取元素递归。

步骤分析

1. 输入数组：nums = [1, 2, 3]。
2. 递归机制：
   • 每次递归时，直接将当前路径加入结果集。
   • 从当前位置 pos 开始，依次向后选择元素，尝试递归。

运行示例

• 初始调用：dfs(nums, 0)
  • 当前路径为空，加入结果集：ret = [[]]
  • 从 pos = 0 开始：
    • 选 1：path = [1]，加入结果集：ret = [[], [1]]，递归进入 dfs(nums, 1)
      • 选 2：path = [1, 2]，加入结果集：ret = [[], [1], [1, 2]]，递归进入 dfs(nums, 2)
        • 选 3：path = [1, 2, 3]，加入结果集：ret = [[], [1], [1, 2], [1, 2, 3]]
        • 回溯到选 2 状态：path = [1, 2]
      • 回溯到选 1 状态：path = [1]
    • 回溯到初始状态：path = []
    • 选 2：递归同上。
    • 选 3：递归继续。

代码

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos) {
        ret.push_back(path);
        for (int i = pos; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            // 回溯 -> 恢复现场
            path.pop_back();
        }
    }
};

时间复杂度分析

解法一

1. 决策树分析：
   • 每个元素有两种选择（选或不选），对于长度为 n 的数组，共有 2^n 种子集。
   • 递归的每一步都对应一个子集的生成，因此遍历整个决策树需要 O(2^n) 的时间。
2. 额外操作：
   • 每次递归终止时，将当前路径 path 加入结果，需要 O(n) 的时间（复制 path 的内容）。

总时间复杂度：O(2^n · n)

解法二

1. 决策树分析：
   • 每个元素被递归遍历一次，所有可能的子集共 2^n 个。
   • 递归过程中，每次递归都会将当前路径 path 加入结果集 ret。
2. 额外操作：
   • 每次将路径加入结果集也需要 O(n) 的时间（复制 path）。

总时间复杂度：O(2^n · n)

空间复杂度分析

解法一

1. 递归深度：
   • 递归调用的最大深度为数组长度 n，因此递归栈的空间复杂度为 O(n)。
2. 路径存储：
   • path 需要存储当前路径，大小为 O(n)。
3. 结果集：
   • 最终结果集 ret 包含 2^n 个子集，每个子集的平均长度为 O(n/2)，因此结果集的存储空间为：O(2^n · n)

总空间复杂度：O(2^n · n)（递归栈和路径空间较小，可忽略不计）

解法二

1. 递归深度：
   • 递归调用的最大深度为数组长度 n，因此递归栈的空间复杂度为 O(n)。
2. 路径存储：
   • path 需要存储当前路径，大小为 O(n)。
3. 结果集：
   • 同解法一，结果集需要 O(2^n · n) 的空间。

总空间复杂度：O(2^n · n)（递归栈和路径空间较小，可忽略不计）

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

题目链接：https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/

解法简介

题目要求求出数组中所有子集的异或和的总和。解法采用 回溯法 (Backtracking)，枚举所有子集，同时计算每个子集的异或和，并将其累加到结果中。

解法步骤

Step 1: 初始化变量

• ret：最终结果，用于存储所有子集的异或和的累加值。
• path：当前路径变量，表示当前子集的异或值。
• nums：输入数组。

Step 2: 回溯递归函数设计

递归函数 dfs(nums, pos)：

1. 功能：
   • 遍历以 pos 为起点的所有可能子集。
   • 累加每个子集的异或值到 ret。
2. 核心逻辑：
   • 累加当前路径的异或值到 ret：每次递归进入时，将当前路径的异或值（path）加入到结果中。
   • 枚举后续元素：从当前 pos 开始，逐一尝试将后续元素加入路径 path，并递归处理。
   • 回溯：在递归返回后，撤销当前选择（通过异或运算恢复 path 的值）。
3. 递归终止条件：
   • 无需显式终止条件，因为递归自然会遍历所有子集，当 pos 超出数组范围时，循环自动结束。

Step 3: 主函数调用

在主函数 subsetXORSum 中：

1. 初始化结果变量 ret = 0。
2. 调用回溯函数：dfs(nums, 0)，从数组的第 0 个位置开始递归。
3. 返回最终结果 ret。

代码

class Solution {
public:
    int ret = 0;
    int path = 0;

    int subsetXORSum(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos) {
        ret += path;
        for (int i = pos; i < nums.size(); i++) {
            path ^= nums[i];
            dfs(nums, i + 1);
            // 回溯
            path ^= nums[i];
        }
    }
};

时间与空间复杂度

时间复杂度

1. 子集数量：对于数组长度为 n，共有 2^n 个子集。
2. 异或计算：每次递归执行异或操作的时间复杂度为 O(1)。
3. 总复杂度：O(2^n)

空间复杂度

1. 递归深度：递归调用栈的最大深度为 n。
2. 路径变量：path 是一个整数，占用 O(1) 的空间。
3. 总复杂度：O(n)

四、全排列 II

题目链接：https://leetcode.cn/problems/permutations-ii/description/

解法简介

利用 回溯法 (Backtracking) 生成所有排列，通过排序和剪枝（跳过重复元素）来避免生成重复排列。

步骤详解

Step 1: 初始化

1. 变量说明：
   • ret：存储所有结果的二维数组。
   • path：当前路径，用于构造一个排列。
   • check：布尔数组，记录每个元素是否已经被使用过。
2. 预处理：
   • 对输入数组 nums 进行排序：sort(nums.begin(), nums.end())。
     • 排序的目的是将相同的元素放在一起，方便后续剪枝操作。

Step 2: 回溯递归函数设计

递归函数 dfs(nums, pos)：

1. 递归终止条件：
   • 如果当前路径 path 的大小等于数组 nums 的长度，说明构造了一组完整排列，将其加入结果集 ret。
2. 循环遍历每个元素：
   • 遍历 nums 中的每个元素，尝试将未被使用的元素加入当前路径。
3. 剪枝条件：
   • 元素未被使用：通过 check[i] == false 判断当前元素是否可用。
   • 跳过重复元素：
     • nums[i] == nums[i - 1]：当前元素与前一个元素相同。
     • check[i - 1] == false：前一个相同的元素尚未被使用，说明该排列已经处理过，直接跳过当前分支。
4. 递归和回溯：
   • 递归调用：
     • 将当前元素加入路径，标记为已使用。
     • 递归处理下一个位置。
   • 回溯操作：
     • 递归返回后，将当前元素移出路径，标记为未使用，恢复状态。

Step 3: 主函数调用

在主函数 permuteUnique 中：

1. 对数组排序：sort(nums.begin(), nums.end())。
2. 初始化布尔数组：check 的大小为 nums.size()，初始值为 false。
3. 调用回溯函数：dfs(nums, 0)。
4. 返回结果集 ret。

代码

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[9];

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        // 先排序
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos) {
        if (path.size() == nums.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // 剪枝（只关心合法分支）
            if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums, pos + 1);
                // 回溯
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

时间与空间复杂度

时间复杂度

1. 全排列生成：
   • 数组长度为 n，排列数量为 n!。
2. 剪枝优化：
   • 剪枝减少重复分支，但在最坏情况下仍需要生成 n! 个排列。

总时间复杂度：O(n · n!)

空间复杂度

1. 递归深度：
   • 递归调用栈的深度为 O(n)。
2. 路径和标记数组：
   • 路径数组 path 和布尔数组 check 的大小为 O(n)。

总空间复杂度：O(n)

结语

回溯法与深度优先搜索（DFS）结合，能有效地解决多种组合问题。通过决策树的结构，回溯法逐步探索解空间，而剪枝则通过减少不必要的计算，显著提高算法的效率。针对特定问题的剪枝优化，可以进一步提升回溯法的性能。