# LeetCode 46: Permutations

## Problem Restatement

We are given an array `nums` containing distinct integers.

We need to return all possible permutations of the array. A permutation is one possible ordering of all elements.

The answer may be returned in any order. The official problem states: given an array `nums` of distinct integers, return all possible permutations.

Example:

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

The possible permutations are:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array `nums` of distinct integers |
| Output | A list of all possible permutations |
| Rule | Each permutation must use every number exactly once |
| Order | The returned permutations may be in any order |

Function shape:

```python
def permute(nums: list[int]) -> list[list[int]]:
    ...
```

## First Thought: Build Every Ordering

A permutation is an ordering of all numbers.

For each position, we can choose any number that has not already been used.

For example, with:

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

At the first position, we can choose `1`, `2`, or `3`.

If we choose `1`, then the next position can choose `2` or `3`.

If we choose `2`, then the next position can choose `1` or `3`.

This forms a decision tree.

Backtracking is a natural fit because we build one partial permutation, explore it, then undo the last choice and try another choice.

## Key Insight

Use a temporary list called `path`.

`path` stores the permutation currently being built.

Also use a boolean array called `used`.

`used[i]` tells us whether `nums[i]` is already inside `path`.

When `path` has the same length as `nums`, we have built one full permutation. Add a copy of `path` to the answer.

The copy matters because `path` will continue changing during backtracking.

## Algorithm

Initialize:

```python
ans = []
path = []
used = [False] * len(nums)
```

Define a recursive function `backtrack()`.

Inside `backtrack()`:

1. If `len(path) == len(nums)`, append a copy of `path` to `ans`.
2. Otherwise, loop through each index `i`.
3. If `used[i]` is true, skip it.
4. Choose `nums[i]`.
5. Mark it as used.
6. Recurse.
7. Undo the choice by popping from `path` and marking it unused.

Return `ans`.

## Walkthrough

Use:

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

Start:

```python
path = []
used = [False, False, False]
```

Choose `1`:

```python
path = [1]
used = [True, False, False]
```

Choose `2`:

```python
path = [1, 2]
used = [True, True, False]
```

Choose `3`:

```python
path = [1, 2, 3]
used = [True, True, True]
```

Now the path length is `3`, so we append:

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

Then backtrack.

Remove `3`, then try the next available choice after `2`. There is no next choice, so remove `2`.

Now from:

```python
path = [1]
used = [True, False, False]
```

choose `3`, then choose `2`.

This gives:

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

The recursion continues until every first choice has been explored.

Final result:

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

## Correctness

The algorithm builds permutations one position at a time.

At each recursive call, `path` contains distinct elements from `nums`, because a number can be added only when its corresponding `used[i]` value is false.

When `len(path) == len(nums)`, the path contains exactly `n` distinct elements chosen from an array of length `n`. Therefore, it contains every element exactly once, so it is a valid permutation.

The loop tries every unused number at each position. Therefore, for any valid permutation, the algorithm can follow the exact sequence of choices that creates it.

Backtracking restores the state after each choice, so choices from one branch do not block choices in another branch.

Thus, the algorithm generates every valid permutation, and because each position uses an unused number, it never generates an invalid permutation.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * n!)` | There are `n!` permutations, and copying each full path costs `O(n)` |
| Space | `O(n)` | The recursion stack, `path`, and `used` array each use linear space |

The output itself contains `n!` permutations, each of length `n`, so the returned answer uses `O(n * n!)` space.

## Implementation

```python
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        ans = []
        path = []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(path) == len(nums):
                ans.append(path[:])
                return

            for i in range(len(nums)):
                if used[i]:
                    continue

                used[i] = True
                path.append(nums[i])

                backtrack()

                path.pop()
                used[i] = False

        backtrack()
        return ans
```

## Code Explanation

We store all finished permutations in:

```python
ans = []
```

The current partial permutation is:

```python
path = []
```

The `used` array prevents using the same element twice:

```python
used = [False] * len(nums)
```

The base case is:

```python
if len(path) == len(nums):
```

At this point, `path` is a complete permutation.

We append a copy:

```python
ans.append(path[:])
```

Then we try each number:

```python
for i in range(len(nums)):
```

If it is already used, skip it:

```python
if used[i]:
    continue
```

Otherwise, choose it:

```python
used[i] = True
path.append(nums[i])
```

Then recurse.

After recursion returns, undo the choice:

```python
path.pop()
used[i] = False
```

This reset is what allows the next branch to start from a clean state.

## Testing

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

def run_tests():
    s = Solution()

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

    assert normalize(s.permute([0, 1])) == normalize([
        [0, 1],
        [1, 0],
    ])

    assert normalize(s.permute([1])) == normalize([
        [1],
    ])

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

    print("all tests passed")

run_tests()
```

| Test | Expected Count | Reason |
|---|---:|---|
| `[1, 2, 3]` | `6` | Standard three-element case |
| `[0, 1]` | `2` | Small two-element case |
| `[1]` | `1` | Single element has one permutation |
| `[-1, 2]` | `2` | Negative values work the same way |