Permutations

Given the array [1, 2, 3], how many ways can you arrange all three elements? The answer is six: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. Every element appears exactly once in each arrangement, but the order differs. Generating all permutations is a classic backtracking problem, and it differs from subsets and combinations in a fundamental way.

How Permutations Differ from Subsets and Combinations

With subsets and combinations, order does not matter: [1, 2] and [2, 1] are the same subset. To enforce that, you use a start index that only looks forward through the array. With permutations, order matters: [1, 2, 3] and [3, 2, 1] are different answers. There is no start index. Instead, at each position in the permutation, you consider every element in the array and skip the ones you have already placed.

This means you need a way to track which elements are currently in use. The most common approach is a boolean array called used, the same length as the input. When you place an element into the path, you mark it as used. When you backtrack, you unmark it. At each step, you loop over all elements and only recurse on the unused ones.

The Used-Array Approach

The algorithm builds the permutation one position at a time. At each recursive call, you loop through every element. If the element is not used, you mark it used, append it to the path, and recurse. When the path reaches length n, you have a complete permutation and record it. On the way back, you pop the element and unmark it.

Walking Through the Recursion Tree for [1, 2, 3]

We start with bt([]), used = [F, F, F].

Loop over i = 0, 1, 2. All are unused.

i = 0: mark used[0], path = [1]. Recurse.

Inside, loop i = 0, 1, 2. i = 0 is used, skip. i = 1: mark used[1], path = [1, 2]. Recurse.

Inside, i = 0 used, i = 1 used, i = 2: mark used[2], path = [1, 2, 3]. Length equals 3, so record [1, 2, 3]. Unmark 2, pop to [1, 2].

Back up: unmark 1, pop to [1]. Now i = 2: mark used[2], path = [1, 3]. Recurse.

Inside, i = 0 used, i = 1 free: path = [1, 3, 2]. Record it. Backtrack.

Unmark 2, pop to [1]. Unmark 0, pop to [].

Now i = 1 at the root: path = [2]. Inside, i = 0 free: path = [2, 1]. Then i = 2 free: path = [2, 1, 3]. Record. Backtrack. Then i = 2 at second level: path = [2, 3]. i = 0 free: path = [2, 3, 1]. Record. Backtrack all the way.

i = 2 at root: path = [3]. Produces [3, 1, 2] and [3, 2, 1].

Final result: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1], all six permutations.

Code: Permutations

For LeetCode 46, the implementation is as follows.

def permute(nums):
    res = []
    used = [False] * len(nums)

    def bt(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt(path)
            path.pop()
            used[i] = False

    bt([])
    return res

Each permutation is recorded only when the path reaches full length. This is a "collect at leaf nodes" pattern, just like combinations of size k. The difference is there is no start index; the used array prevents reuse instead.

Permutations II: Handling Duplicates

LeetCode 47 extends this: when the input contains duplicates, like [1, 1, 2], the basic algorithm would produce duplicate permutations. Both 1s are interchangeable, so placing the first 1 at position 0 and the second 1 at position 1 gives the same result as the reverse.

The fix is to sort the array and add a skip rule: if nums[i] == nums[i - 1] and used[i - 1] is False, skip nums[i]. This rule requires that among duplicate values, they are used in order: you cannot use the second copy unless the first copy is already in the path.

Why the Skip Condition Works

Consider [1, 1, 2] after sorting. Call the two 1s "1a" (index 0) and "1b" (index 1).

Without the skip rule, the algorithm would try placing 1a at position 0 then 1b at position 1, and also 1b at position 0 then 1a at position 1. Both produce [1, 1, 2].

The skip rule says: you cannot place 1b unless 1a is already used. So 1b at position 0 while 1a is unused? Skip. This forces 1a to always come before 1b when both are in the path, eliminating the symmetry.

More precisely: at any level of the recursion tree, the condition i > 0 and nums[i] == nums[i - 1] and not used[i - 1] prevents the same value from being chosen at the same position twice. The first duplicate is always preferred over the second, the second over the third, and so on.

Walking Through Permutations of [1, 1, 2]

Sorted input: [1, 1, 2]. used = [F, F, F].

Root level, i = 0: place 1a. used = [T, F, F], path = [1].

Second level, i = 0 used. i = 1: nums[1] == nums[0] and used[0] is True, so the condition is not met and we do NOT skip. Place 1b. used = [T, T, F], path = [1, 1].

Third level, i = 2: place 2. path = [1, 1, 2]. Record. Backtrack to [1, 1], unmark 2. Backtrack to [1], unmark 1b.

Second level, i = 2: place 2. path = [1, 2]. Third level, i = 1: nums[1] == nums[0] but used[0] is True, so allow. Place 1b. path = [1, 2, 1]. Record. Backtrack.

Back to root, unmark 1a. i = 1: nums[1] == nums[0] and used[0] is False, so the skip condition is met. Skip 1b. This prevents placing 1b first, which would duplicate the permutations we already generated with 1a first.

Root level, i = 2: place 2. path = [2]. Second level, i = 0: place 1a. path = [2, 1]. Third level, i = 1: allow 1b (1a is used). path = [2, 1, 1]. Record. Backtrack.

Second level, i = 1: nums[1] == nums[0] and used[0] is False, so skip.

Final result: [1, 1, 2], [1, 2, 1], [2, 1, 1]. Three unique permutations.

Code: Permutations II

def permute_unique(nums):
    nums.sort()
    res = []
    used = [False] * len(nums)

    def bt(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            bt(path)
            path.pop()
            used[i] = False

    bt([])
    return res

The sorting step is essential: the skip rule relies on duplicates being adjacent.

The Swap-Based Approach

There is an alternative way to generate permutations that avoids the used array entirely. Instead of building a separate path, you rearrange the input array in place. At each recursion level, you pick which element goes in position idx by swapping each candidate into that position, recursing to fill the remaining positions, then swapping back.

def permute_swap(nums):
    res = []

    def bt(idx):
        if idx == len(nums):
            res.append(nums[:])
            return
        for i in range(idx, len(nums)):
            nums[idx], nums[i] = nums[i], nums[idx]
            bt(idx + 1)
            nums[idx], nums[i] = nums[i], nums[idx]

    bt(0)
    return res

At level idx, elements before idx are fixed in the permutation. We try each element from index idx onward by swapping it into position idx, then recursing to fix position idx + 1. This approach uses $O(1)$ extra space beyond the recursion stack, since the array itself holds the partial permutation.

The swap-based approach is elegant but harder to extend to duplicate handling, because the swaps can disrupt the sorted order that the skip rule depends on. For problems with duplicates, the used-array approach is generally cleaner.

Next Permutation: The Iterative Approach

Take LeetCode 31: not all permutation problems require generating every arrangement. Sometimes you need just the next permutation in lexicographic order. Given [1, 3, 2], the next permutation is [2, 1, 3]. This is a completely different algorithm: no backtracking, no recursion, just a three-step procedure.

The algorithm works by finding the rightmost place where the sequence is still ascending, making the smallest possible increment there, and then minimizing everything to the right.

Step 1: scan from right to left to find the first index i where nums[i] < nums[i + 1]. This is the "pivot," the rightmost position where an increase is possible. Everything to the right of i is in descending order (otherwise i would not be the rightmost ascent).

Step 2: scan from the right again to find the smallest element that is larger than nums[i]. Call this index j. Swap nums[i] and nums[j].

Step 3: reverse the suffix after index i. Since the suffix was in descending order, reversing it produces the smallest possible arrangement of those elements: the lexicographically smallest suffix.

If no ascending pair exists in step 1, the array is in fully descending order (the last permutation). In that case, reverse the entire array to wrap around to the first permutation.

Walking Through Next Permutation of [1, 3, 2]

We have nums = [1, 3, 2].

Step 1: scan from right. Compare index 2 and 1: nums[1] = 3 > nums[2] = 2, so no ascent here. Compare index 1 and 0: nums[0] = 1 < nums[1] = 3. Found it. The pivot is i = 0.

Step 2: scan from right to find the first element greater than nums[0] = 1. At index 2, nums[2] = 2 > 1. So j = 2. Swap nums[0] and nums[2]: array becomes [2, 3, 1].

Step 3: reverse the suffix after index 0. The suffix is [3, 1]. Reversed: [1, 3]. Final array: [2, 1, 3].

And indeed [2, 1, 3] is the lexicographic successor of [1, 3, 2] among permutations of {1, 2, 3}.

Code: Next Permutation

def next_permutation(nums):
    n = len(nums)

    # Step 1: find the rightmost ascent
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: find the rightmost element larger than nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    # Step 3: reverse the suffix after i
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

This modifies the array in place. The algorithm runs in $O(n)$ time and $O(1)$ space, with no recursion and no extra arrays. When i ends up at -1 (no ascending pair found), the algorithm skips the swap and just reverses the entire array, wrapping from the last permutation back to the first.

Complexity Analysis

For basic permutations of $n$ distinct elements, there are $n!$ permutations and each has length $n$, so the total time is $O(n \cdot n!)$. The recursion depth is $n$, and the used array takes $O(n)$ space, so auxiliary space is $O(n)$.

For permutations with duplicates, the number of unique permutations is $n!$ divided by the product of $k!$ for each group of $k$ identical elements. The algorithm with the skip rule generates exactly these unique permutations, so it is efficient relative to the output size.

The swap-based approach has the same $O(n \cdot n!)$ time complexity but avoids the $O(n)$ used array, using only $O(n)$ for the recursion stack.

Next Permutation runs in $O(n)$ time and $O(1)$ space, making it suitable for problems that need just a single step forward in the permutation sequence rather than full enumeration.

Recognizing this pattern

You're probably looking at permutation backtracking when:

• The problem asks for all orderings or arrangements of a sequence.
• Input size is tiny, typically n ≤ 10, because n! explodes quickly.
• You need the next or previous permutation in lexicographic order.
• The phrasing involves "all arrangements", "all permutations", or "k-th permutation sequence".

Common templates:

• Used-array recursion: track which indices are taken, pick an unused element at each level. Example: Permutations.
• Swap-in-place: at each recursion depth, swap each remaining element into the current slot. Example: Permutations.
• Sorted + skip duplicates: sort first, then skip equal siblings to avoid repeated outputs. Example: Permutations II.
• Next permutation in place: find pivot, swap, reverse suffix; O(n) / O(1). Example: Next Permutation.