python - 返回给定列表的所有可能子集会返回错误答案

Question

我目前正在练习一个面试问题，并且正在做一个必须返回给定列表的所有可能子集的问题。

例如，

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

就是答案。

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        subset = []
        self.backtrack(sorted(nums), res, subset, 0)
        return res

    def backtrack(self, nums, res, subset, start):
        res.append(list(subset))
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            subset.append(nums[i])
            self.backtrack(nums, res, subset, start + 1)
            subset.pop()

我的解决方案如上，使用回溯。我检查了条件 if i > start and nums[i] == nums[i - 1] 来处理重复项。但是，我的输出是 [[],[1],[1,2],[1,2,2],[2],[2,2],[2,2,2]]，给出了一个不应该生成的额外的 [2, 2, 2] 。

我按照我的代码画了一个图表，但仍然不明白为什么会生成这个图表。不是应该在那之前终止吗？

谢谢

Answer 1

isValidSubset 函数在 nums 和子集之间进行减法运算，因此对于 [1,2,2] - [2,2,2] 保留 2 并希望成为有效子集

def subsetsWithDup(nums):
    res = []
    subset = []
    backtrack(sorted(nums), res, subset, 0)
    return res


def isValidSubset(s, n):
    nums = s.copy()
    subset = n.copy()
    return len([i for i in nums if not i in subset or subset.remove(i)]) == 0


def backtrack(nums, res, subset, start):
    if (isValidSubset(subset, nums)):
        res.append(list(subset))
    for i in range(start, len(nums)):
        if i > start and nums[i] == nums[i - 1]:
            continue
        subset.append(nums[i])
        backtrack(nums, res, subset, start + 1)
        subset.pop()


a = [1, 2, 2]
b = [2, 2, 2]

print(subsetsWithDup(a))