LeetCode 90: Subsets Ii — Step-by-Step Visual Trace

#python #leetcode #algorithms

Medium — Backtracking | Array | Bit Manipulation

The Problem

Given an integer array that may contain duplicates, return all possible subsets (the power set) without duplicate subsets in the result.

Approach

Use backtracking to generate all subsets by making include/exclude decisions for each element. Sort the array first, then skip duplicate elements at the same recursion depth level to avoid generating duplicate subsets.

Time: O(2^n * n) · Space: O(n)

Code

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, subset):
            subsets.append(subset[:])  # Append a copy of the current subset

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue  # Skip duplicates at the same depth level
                subset.append(nums[i])
                backtrack(i + 1, subset)
                subset.pop()  # Backtrack

        nums.sort()  # Sort the input to handle duplicates
        subsets = []
        backtrack(0, [])
        return subsets