LeetCode 46 - Permutations

The problem gives us an array of distinct integers called nums, and asks us to generate every possible permutation of those numbers. A permutation is an arrangement of elements in a specific order.

leetcodemediumarraybacktracking

LeetCode Problem 46

Difficulty: 🟡 Medium
Topics: Array, Backtracking

Solution

LeetCode 46 - Permutations

Problem Understanding

The problem gives us an array of distinct integers called nums, and asks us to generate every possible permutation of those numbers.

A permutation is an arrangement of elements in a specific order. For example, if the input is [1,2,3], then [1,2,3], [1,3,2], and [2,1,3] are all different permutations because the order of elements changes.

The input array contains unique integers, which simplifies the problem because we do not need to handle duplicate permutations. Our task is to return a list containing every possible ordering of the input numbers.

The constraints are small:

  • 1 <= nums.length <= 6
  • All values are unique

Since the maximum length is only 6, the total number of permutations is at most:

$$6! = 720$$

This tells us that generating all permutations directly is feasible. In fact, any correct solution must spend at least O(n!) time because there are n! outputs.

There are several important edge cases to keep in mind:

  • A single-element array such as [1] should return [[1]]
  • A two-element array should return exactly two permutations
  • Negative numbers must work exactly the same as positive numbers
  • Since all numbers are distinct, we never need duplicate checking logic
  • The algorithm must ensure that every permutation has exactly n elements and no repeated elements inside a single permutation

The core challenge is systematically exploring every valid ordering without missing any possibilities.

Approaches

Brute Force Approach

A brute force strategy would try every possible ordering of the numbers and check whether it forms a valid permutation.

One way to do this is:

  1. Generate every sequence of length n
  2. Allow repeated choices while building sequences
  3. Filter out sequences that reuse elements

For example, with [1,2,3], we could generate all possible sequences of length 3:

  • [1,1,1]
  • [1,1,2]
  • [1,1,3]
  • ...
  • [3,3,3]

Then we would keep only the sequences where every number appears exactly once.

This approach is correct because every valid permutation will eventually appear among all generated sequences. However, it is extremely inefficient because it generates many invalid combinations that must later be discarded.

The total number of generated sequences would be:

$$n^n$$

which grows much faster than n!.

Optimal Backtracking Approach

The better approach is to construct permutations incrementally while enforcing validity during construction.

The key insight is that at every position in the permutation, we only need to choose from numbers that have not already been used.

This naturally leads to backtracking:

  • Build the permutation one element at a time
  • Keep track of which numbers are already used
  • Once the permutation reaches length n, save it
  • Backtrack by removing the last choice and trying another option

Instead of generating invalid states and filtering later, we only generate valid partial permutations throughout the search.

Because the constraints are small and every permutation must eventually be produced, this is the optimal practical solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^n) O(n^n) Generates all sequences and filters invalid ones
Optimal Backtracking O(n × n!) O(n) excluding output Builds only valid permutations incrementally

Algorithm Walkthrough

Optimal Backtracking Algorithm

  1. Create an empty result list that will store all permutations.
  2. Maintain a temporary list called current_permutation. This represents the permutation currently being built.
  3. Maintain a boolean array called used. Each index corresponds to a number in nums. If used[i] is True, it means that nums[i] is already included in the current permutation.
  4. Define a recursive backtracking function.
  5. Inside the recursive function, first check whether the current permutation length equals the length of nums.
  6. If the lengths match, we have completed a valid permutation. Append a copy of the current permutation to the result list.
  7. Otherwise, iterate through every number in nums.
  8. For each number:

  • Skip it if it has already been used

  • Otherwise:

  • Mark it as used

  • Add it to the current permutation

  • Recursively continue building the permutation

  1. After recursion returns, undo the choice:
  • Remove the last element from the current permutation
  • Mark the number as unused again
  1. Continue trying the remaining choices until all possibilities are explored.

Why it works

The algorithm maintains an important invariant:

  • At every recursive level, current_permutation contains only unique elements chosen from nums

Because we only choose unused elements, no permutation can contain duplicates. Because recursion continues until length n, every completed permutation contains every number exactly once.

Backtracking systematically explores every valid choice at every position, guaranteeing that all permutations are generated exactly once.

Python Solution

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        current_permutation = []
        used = [False] * len(nums)

        def backtrack():
            if len(current_permutation) == len(nums):
                result.append(current_permutation[:])
                return

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

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

                backtrack()

                current_permutation.pop()
                used[i] = False

        backtrack()

        return result

The implementation begins by initializing three structures:

  • result stores all completed permutations
  • current_permutation stores the permutation currently being built
  • used tracks which elements are already included

The nested backtrack() function performs the recursive exploration.

The base case occurs when the current permutation length matches the input length. At that point, a complete permutation has been formed, so a copy is appended to the result list.

The loop iterates through all indices in nums. If a number has already been used in the current permutation, it is skipped.

When a number is selected:

  • It is marked as used
  • Added to the current permutation
  • Recursion continues

After recursion finishes exploring that branch, the algorithm backtracks:

  • The last number is removed
  • The used marker is reset

This restores the state exactly as it was before the choice, allowing the algorithm to explore the next possibility cleanly.

Go Solution

func permute(nums []int) [][]int {
    result := [][]int{}
    currentPermutation := []int{}
    used := make([]bool, len(nums))

    var backtrack func()

    backtrack = func() {
        if len(currentPermutation) == len(nums) {
            permutationCopy := make([]int, len(currentPermutation))
            copy(permutationCopy, currentPermutation)

            result = append(result, permutationCopy)
            return
        }

        for i := 0; i < len(nums); i++ {
            if used[i] {
                continue
            }

            used[i] = true
            currentPermutation = append(currentPermutation, nums[i])

            backtrack()

            currentPermutation = currentPermutation[:len(currentPermutation)-1]
            used[i] = false
        }
    }

    backtrack()

    return result
}

The Go implementation follows the same recursive backtracking logic as the Python solution.

One important difference is slice handling. In Go, slices reference underlying arrays, so we must explicitly create a copy before appending a completed permutation to result. Otherwise, later modifications would affect previously stored permutations.

The statement:

permutationCopy := make([]int, len(currentPermutation))
copy(permutationCopy, currentPermutation)

ensures that each stored permutation is independent.

Go does not have concerns about integer overflow here because the input values and recursion depth are very small.

Worked Examples

Example 1

Input:

nums = [1,2,3]

Initial state:

Variable Value
current_permutation []
used [False, False, False]

Choose 1 first:

Action current_permutation used
Add 1 [1] [True, False, False]

Now choose 2:

Action current_permutation used
Add 2 [1,2] [True, True, False]

Now choose 3:

Action current_permutation used
Add 3 [1,2,3] [True, True, True]

Length equals n, so append:

[1,2,3]

Backtrack:

Action current_permutation
Remove 3 [1,2]

Try another choice, none remain.

Backtrack again:

Action current_permutation
Remove 2 [1]

Now choose 3:

Action current_permutation
Add 3 [1,3]

Then choose 2:

Action current_permutation
Add 2 [1,3,2]

Append:

[1,3,2]

The process continues similarly for prefixes [2] and [3].

Final output:

[
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
]

Example 2

Input:

nums = [0,1]

Recursive exploration:

Step current_permutation
Start []
Choose 0 [0]
Choose 1 [0,1]
Save permutation [0,1]
Backtrack [0]
Backtrack []
Choose 1 [1]
Choose 0 [1,0]
Save permutation [1,0]

Final output:

[[0,1],[1,0]]

Example 3

Input:

nums = [1]

Execution:

Step current_permutation
Start []
Choose 1 [1]
Save permutation [1]

Final output:

[[1]]

Complexity Analysis

Measure Complexity Explanation
Time O(n × n!) There are n! permutations, and copying each permutation takes O(n)
Space O(n) excluding output Recursion depth and auxiliary structures store at most n elements

The algorithm generates every permutation exactly once. Since there are n! permutations and each permutation contains n elements, the total work is O(n × n!).

The recursion stack, current permutation, and used array each require at most O(n) space. The output itself requires O(n × n!) storage, but this is typically excluded from auxiliary space analysis.

Test Cases

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        current_permutation = []
        used = [False] * len(nums)

        def backtrack():
            if len(current_permutation) == len(nums):
                result.append(current_permutation[:])
                return

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

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

                backtrack()

                current_permutation.pop()
                used[i] = False

        backtrack()

        return result

solution = Solution()

# Example 1
assert sorted(solution.permute([1, 2, 3])) == sorted([
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1]
])  # Standard three-element permutation case

# Example 2
assert sorted(solution.permute([0, 1])) == sorted([
    [0, 1],
    [1, 0]
])  # Two-element input

# Example 3
assert solution.permute([1]) == [[1]]  # Single-element edge case

# Negative numbers
assert sorted(solution.permute([-1, 2])) == sorted([
    [-1, 2],
    [2, -1]
])  # Handles negative values correctly

# Four elements
result = solution.permute([1, 2, 3, 4])
assert len(result) == 24  # 4! permutations expected

# Ensure no duplicates
result = solution.permute([1, 2, 3])
assert len(result) == len(set(tuple(p) for p in result))  # Every permutation unique

# Check permutation lengths
result = solution.permute([5, 6, 7])
assert all(len(p) == 3 for p in result)  # Every permutation has correct length

# Boundary size test
result = solution.permute([1, 2, 3, 4, 5, 6])
assert len(result) == 720  # Maximum constraint size
Test Why
[1,2,3] Validates standard permutation generation
[0,1] Tests minimal multi-element input
[1] Tests smallest possible input
[-1,2] Ensures negative numbers work correctly
[1,2,3,4] Verifies factorial growth behavior
Duplicate check Ensures permutations are unique
Length validation Confirms all permutations are complete
[1,2,3,4,5,6] Tests maximum input constraint

Edge Cases

Single Element Input

An input such as [1] is the smallest valid case. A buggy implementation might accidentally return an empty list instead of a list containing one permutation.

The implementation handles this correctly because the recursion immediately reaches the base case after selecting the single element, producing [[1]].

Backtracking State Corruption

A common bug in recursive backtracking solutions occurs when the algorithm forgets to undo state changes after recursion returns.

For example, if we forget to:

  • remove the last element from the permutation
  • reset the used marker

then later recursive branches would operate on corrupted state and produce incorrect results.

The implementation explicitly restores both structures after every recursive call, guaranteeing clean exploration of all branches.

Mutable List Reference Issues

Another subtle issue appears when appending permutations to the result list.

If we append the same mutable list object repeatedly without copying it, later modifications will affect all stored permutations.

For example:

result.append(current_permutation)

would be incorrect.

The implementation avoids this by appending a copy:

result.append(current_permutation[:])

This guarantees each stored permutation remains independent even after backtracking modifies the working list.