Returning all possible subsets given a list returns wrong answer

Question

I am currently practicing an interview question and doing the one in which I have to return all possible subsets given a list.

For example,

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

is the answer.

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()

My solution is as above, using backtracking. I checked the condition if i > start and nums[i] == nums[i - 1] to handle duplicates. However, my output is [[],[1],[1,2],[1,2,2],[2],[2,2],[2,2,2]], giving an extra [2, 2, 2] which is not supposed to be generated.

I drew a diagram following my code, but still don't get why this is getting generated. Isn't it supposed to terminate before that?

Thanks

Answer 1

isValidSubset function do substruction between nums to subset so for [1,2,2] - [2,2,2] remain 2 and want be a valid subset

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))