如何用DFS求含重复元素数组的幂集？正确剪枝策略是什么？

给定包含重复元素的整数数组nums，需返回所有可能的子集（幂集），且解集不能包含重复子集，返回顺序不限。

• 示例1：输入nums = [1,2,2]，输出[[],[1],[1,2],[1,2,2],[2],[2,2]]
• 示例2：输入nums = [0]，输出[[],[0]]

原代码问题 #

原代码剪枝逻辑错误，导致输入[1,2,2]时输出[[], [1], [1, 2], [2]]，缺失[1,2,2]和[2,2]两个合法子集。原代码如下：

def dfs(nums, result, index, subset):
    result.append(subset.copy())
    if index == len(nums):
        return
    for i in range(index, len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        subset.append(nums[i])
        dfs(nums, result, i + 1, subset)
        subset.pop()

if __name__ == '__main__':
    nums = [1, 2, 2]
    result = []
    dfs(nums, result, 0, [])
    print(result)

正确剪枝策略 #

1. 先排序数组：必须对nums排序，让相同元素相邻，这是去重的基础前提。
2. 调整剪枝条件：将原剪枝条件改为i > index and nums[i] == nums[i - 1]。
   • 逻辑解释：i > index表示当前循环中已跳过同层的前一个相同元素，此时再选重复元素会生成重复子集；而i == index时，允许选择当前元素，以此生成包含多个相同元素的合法子集（如[2,2]）。

修正后的代码 #

def dfs(nums, result, index, subset):
    result.append(subset.copy())
    if index == len(nums):
        return
    for i in range(index, len(nums)):
        # 剪枝：当前元素与前一个相同，且不是当前层第一个可选元素时跳过
        if i > index and nums[i] == nums[i - 1]:
            continue
        subset.append(nums[i])
        dfs(nums, result, i + 1, subset)
        subset.pop()

if __name__ == '__main__':
    nums = [1, 2, 2]
    nums.sort()  # 关键步骤：先排序数组
    result = []
    dfs(nums, result, 0, [])
    print(result)

运行修正后的代码，输入[1,2,2]会输出正确结果：[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]。

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