Q76: Subsets II. - DSA Patterns (Multi-Lang)

In Simple Words: Sort the array first to group identical numbers. In backtracking loop, skip duplicate elements: if i > start && nums[i] === nums[i - 1], continue.

Time: $O(N \cdot 2^N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    def backtrack(start, curr):
        res.append(curr.copy())
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            curr.append(nums[i])
            backtrack(i + 1, curr)
            curr.pop()
    backtrack(0, [])
    return res