回溯法求数组所有子集（幂集） - 解空间树详解

回溯法求数组所有子集（幂集） - 解空间树详解

本文将介绍如何使用回溯法来求解一个包含 n 个不同整数的数组 a 的所有子集（也称为幂集）。

解空间树

回溯法求解子集问题时，会构建一个解空间树来表示所有可能的解。该解空间树是一棵二叉树，其节点表示当前子集的状态：

• 根节点 表示空集。
• 每个节点的左子节点 表示将当前元素加入子集。
• 每个节点的右子节点 表示不将当前元素加入子集。

示例：

假设数组 a 包含 3 个元素：[1, 2, 3]，其解空间树如下：

               []
               / \
              /   \
             /     \
            /       \
           /         \
          /           \
         /             \
        /               \
       /                 \
      /                   \
    [1]                 []
    / \                 / \
   /   \               /   \
  /     \             /     \
[1,2]  [1]           [2]    []
 / \    / \          / \    / \
[1,2,3][1,3]       [2,3]   [3]

算法流程：

1. 从根节点开始遍历解空间树。
2. 对于每个节点，有两种选择：
   • 加入当前元素：沿着左子节点继续遍历。
   • 不加入当前元素：沿着右子节点继续遍历。
3. 当遍历到叶子节点时，该路径表示一个子集。
4. 遍历完所有叶子节点后，就得到了所有子集。

代码实现：

def subsets(nums):
    result = []
    def backtrack(index, current):
        if index == len(nums):
            result.append(current.copy())
            return

        # 选择当前元素
        current.append(nums[index])
        backtrack(index + 1, current)

        # 不选择当前元素
        current.pop()
        backtrack(index + 1, current)

    backtrack(0, [])
    return result

总结：

回溯法通过构建解空间树，并遍历所有路径来求解数组所有子集问题。其核心思想是对于每个元素，都有“选择”和“不选择”两种选择，通过递归的方式遍历所有可能的选择组合。解空间树的结构清晰直观，可以帮助理解回溯算法的执行过程。