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

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

```python
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
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0090_subsets-ii)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0090_subsets-ii) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*