# LeetCode 78: Subsets

## Problem Restatement

We are given an integer array `nums`.

Every element in `nums` is unique.

We need to return all possible subsets of `nums`.

A subset may contain:

| Size | Meaning |
|---|---|
| `0` elements | The empty subset `[]` |
| Some elements | Any valid partial selection |
| All elements | The whole array |

The answer must not contain duplicate subsets. The subsets may be returned in any order.

The official problem states that `nums` contains unique elements and asks for the full power set. The constraints are small: `1 <= nums.length <= 10`, `-10 <= nums[i] <= 10`, and all numbers are unique.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | A list of all subsets |
| Element rule | Every element in `nums` is unique |
| Order rule | Subsets may be returned in any order |
| Duplicate rule | The answer must not contain duplicate subsets |

Function shape:

```python
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3]
```

Each number has two choices:

1. Include it.
2. Exclude it.

The full answer is:

```python
[
    [],
    [1],
    [2],
    [1, 2],
    [3],
    [1, 3],
    [2, 3],
    [1, 2, 3],
]
```

Example 2:

```python
nums = [0]
```

There are only two subsets:

```python
[
    [],
    [0],
]
```

## First Thought: Binary Choice

For each number, we make a decision.

For example:

```python
nums = [1, 2, 3]
```

At `1`, choose:

```python
take 1
skip 1
```

At `2`, choose:

```python
take 2
skip 2
```

At `3`, choose:

```python
take 3
skip 3
```

Since every element has two choices, the number of subsets is:

```python
2^n
```

So any correct solution must produce `2^n` results.

## Key Insight

This problem is a natural backtracking problem.

We build one subset step by step.

At every index `i`, we decide whether `nums[i]` belongs to the current subset.

The recursive state is:

| State | Meaning |
|---|---|
| `i` | Current index in `nums` |
| `path` | Current subset being built |
| `ans` | All subsets found so far |

When `i == len(nums)`, we have made a decision for every element, so `path` is one complete subset.

## Algorithm

Start with:

```python
ans = []
path = []
```

Define:

```python
backtrack(i)
```

At each index `i`:

1. If `i == len(nums)`, copy `path` into `ans`.
2. Otherwise, include `nums[i]`, then recurse.
3. Undo the include choice.
4. Exclude `nums[i]`, then recurse.

This directly models the two choices for each element.

## Walkthrough

Use:

```python
nums = [1, 2]
```

Start with:

```python
path = []
i = 0
```

At `i = 0`, the current number is `1`.

Take `1`:

```python
path = [1]
```

At `i = 1`, the current number is `2`.

Take `2`:

```python
path = [1, 2]
```

Now all decisions are made, so record:

```python
[1, 2]
```

Backtrack and skip `2`:

```python
path = [1]
```

Record:

```python
[1]
```

Backtrack to the first decision and skip `1`:

```python
path = []
```

Then take `2`:

```python
path = [2]
```

Record:

```python
[2]
```

Finally skip `2`:

```python
path = []
```

Record:

```python
[]
```

The result contains every possible subset.

## Correctness

At each index, the algorithm explores exactly two choices: include the current number or exclude it.

A subset of `nums` can be described by one such decision for every index. For example, with three numbers, one subset may correspond to:

```python
include nums[0]
exclude nums[1]
include nums[2]
```

The recursion explores every sequence of such decisions. Therefore, every possible subset is eventually generated.

The algorithm records a subset only when `i == len(nums)`. At that point, every element has already been either included or excluded, so the recorded `path` is a complete valid subset.

No duplicate subsets are generated because each subset corresponds to exactly one include-or-exclude decision sequence. Since `nums` contains unique elements, two different decision sequences cannot produce the same subset.

Therefore, the algorithm returns all valid subsets exactly once.

## Complexity

Let:

```python
n = len(nums)
```

There are `2^n` subsets.

Copying each subset costs up to `O(n)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * 2^n)` | There are `2^n` subsets, and each copied subset may have length up to `n` |
| Extra space | `O(n)` | The recursion stack and current `path` have length at most `n` |
| Output space | `O(n * 2^n)` | The answer stores all subsets |

## Implementation

```python
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        ans = []
        path = []

        def backtrack(i: int) -> None:
            if i == len(nums):
                ans.append(path.copy())
                return

            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

            backtrack(i + 1)

        backtrack(0)
        return ans
```

## Code Explanation

The result list stores all completed subsets:

```python
ans = []
```

The current subset is stored in:

```python
path = []
```

The recursive function receives the current index:

```python
def backtrack(i: int) -> None:
```

When `i` reaches the end, every number has been considered:

```python
if i == len(nums):
    ans.append(path.copy())
    return
```

We copy `path` because `path` is mutable. Without `.copy()`, all answers would refer to the same list object.

The first branch includes the current number:

```python
path.append(nums[i])
backtrack(i + 1)
path.pop()
```

The `pop()` undoes the choice before we explore the second branch.

The second branch excludes the current number:

```python
backtrack(i + 1)
```

Finally, we start from index `0`:

```python
backtrack(0)
```

## Alternative Implementation: Growing Subsets

Another common backtracking style records the current `path` at every call.

Then it tries to add each later number.

```python
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        ans = []
        path = []

        def backtrack(start: int) -> None:
            ans.append(path.copy())

            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return ans
```

This version is often shorter.

It produces the same set of subsets, possibly in a different order.

## Testing

Because LeetCode accepts any order, normalize the result before comparing.

```python
def normalize(result):
    return sorted(tuple(sorted(row)) for row in result)

def run_tests():
    s = Solution()

    assert normalize(s.subsets([1, 2, 3])) == normalize([
        [],
        [1],
        [2],
        [1, 2],
        [3],
        [1, 3],
        [2, 3],
        [1, 2, 3],
    ])

    assert normalize(s.subsets([0])) == normalize([
        [],
        [0],
    ])

    assert normalize(s.subsets([1, 2])) == normalize([
        [],
        [1],
        [2],
        [1, 2],
    ])

    result = s.subsets([4, 5, 6, 7])
    assert len(result) == 16
    assert len(normalize(result)) == 16

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3]` | Main example |
| `[0]` | Smallest valid input |
| `[1, 2]` | Easy to inspect manually |
| `[4, 5, 6, 7]` | Checks count is `2^4 = 16` |
| Unique normalized result count | Confirms no duplicate subsets |