Leetcode 78子集问题：为何生成重复子集且遗漏部分子集？

问题背景 #

给定元素唯一的整数数组nums，返回所有可能的子集（幂集），解集不能包含重复子集，返回顺序不限。编写的代码生成了重复子集且遗漏部分子集，输入nums=[1,2,3]时输出不符合预期。

问题代码 #

def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = []
        expected_subsets = 2**len(nums)
        def generate_subset(subset, nums):
            # base case , gone too far
            if len(subsets) >= expected_subsets:
                return
            if len(subsets) < expected_subsets:
                subsets.append(subset)
            for i in range(len(nums)):
                # choose the current element
                generate_subset(subset+[nums[i]], nums[i+1:])
                # don't choose the current element
                generate_subset(subset, nums[i+1:])
        generate_subset([], nums)
        return subsets

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

[[],[1],[1,2],[1,2,3],[1,2],[1],[1,3],[1]]

预期输出为：

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

关联的Permutations代码（LeetCode 46） #

def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        n = len(nums)
        def dfs(permutation, nums):
            if len(permutation) == n:
                results.append(copy.deepcopy(permutation))
                return
            for i in range(len(nums)):
                permutation.append(nums[i])
                dfs(permutation, nums[:i] + nums[i+1:])
                # backtracking
                permutation.pop()
        dfs([], nums)
        return results

错误原因分析 #

1. 重复子集的产生 #

你的代码在递归逻辑中，同时处理"选当前元素"和"不选当前元素"的分支，但这两个分支会产生重复的递归路径。

以nums=[1,2]为例：

• 初始调用generate_subset([], [1,2])，先添加空集到结果。
• 进入循环i=0：
  • 选1：调用generate_subset([1], [2])，添加[1]到结果。
    • 进入循环i=0：
      • 选2：调用generate_subset([1,2], [])，添加[1,2]到结果。
      • 不选2：调用generate_subset([1], [])，添加[1]到结果（重复）。
  • 不选1：调用generate_subset([], [2])，添加[]到结果（重复）。
    • 进入循环i=0：
      • 选2：调用generate_subset([2], [])，添加[2]到结果。
      • 不选2：调用generate_subset([], [])，添加[]到结果（重复）。

可见，"不选当前元素"的分支会和后续递归中更浅层的路径生成重复子集，因为你在每次递归调用的开头都直接将当前subset加入结果集，导致同一子集被多次添加。

2. 子集遗漏的关联 #

遗漏[2]、[3]等子集的核心原因，是递归路径的覆盖逻辑错误：
当你在"不选当前元素"的分支中调用generate_subset(subset, nums[i+1:])时，这个分支会被前面的"选元素"分支抢先填满结果集（因为你用expected_subsets作为终止条件）。比如在nums=[1,2,3]的场景中，前面的路径（选1、选1+2等）已经生成了8个子集，导致后续"不选1，选2"的分支还没执行，就因为len(subsets) >= expected_subsets被终止了，根本没机会生成[2]、[3]这类子集。

另外，你的递归逻辑没有正确遍历所有"跳过前面元素，选择后面元素"的情况——比如要生成[2]，需要跳过1，直接选择2，但你的代码中，当进入"不选1"的分支后，还没来得及处理选2的逻辑，就被前面的分支填满结果集而终止了。

与Permutations代码的差异 #

Permutations代码的逻辑是每次选择一个未使用的元素加入排列，通过回溯保证每个元素只被选一次，终止条件是排列长度等于原数组长度，不会提前终止。而你的Subsets代码错误地用expected_subsets作为终止条件，且在递归开头就添加子集，导致路径重复和提前终止。

修正思路 #

正确的"选或不选"逻辑应该是：

• 对于每个元素，要么选它（加入当前子集，递归处理剩余元素），要么不选它（直接递归处理剩余元素）。
• 终止条件是处理完所有元素（即nums为空），此时将当前子集加入结果集，而不是在递归开头就添加。

修正后的示例代码：

def subsets(self, nums: List[int]) -> List[List[int]]:
    subsets = []
    def generate_subset(subset, remaining):
        # 处理完所有元素，添加当前子集
        if not remaining:
            subsets.append(subset)
            return
        # 选第一个元素
        generate_subset(subset + [remaining[0]], remaining[1:])
        # 不选第一个元素
        generate_subset(subset, remaining[1:])
    generate_subset([], nums)
    return subsets

这样就能正确生成所有不重复的子集，因为每个元素的选/不选分支是互斥且覆盖所有情况的，不会产生重复路径，也不会提前终止。

内容的提问来源于stack exchange，提问作者Victor Cui