Begin Algo
Recursion & Backtracking · 02 / 05

PermutationsPermutations

A used array, or swapping in place.

Used for: Ordering a schedule, enumerating routes

Time complexityO(n!·n)
Space complexityO(n)
DifficultyIntermediate
PrerequisitesRecursion, subsets

01Why it exists

Job order on a machine

One machine has to process 6 orders, and the changeover time between any two of them differs, so a different order means a different total. You want the sequence that takes the least time.

Why this fitsOrdering problems are not subset problems: the same items in a different order are a different answer. Six orders give 6! = 720 sequences, so you can list them all and total each one. That is the most direct solution to a scheduling problem while n is small, and the starting point for understanding problems like TSP.

Enumerating delivery routes

A courier leaves the depot, has to visit 5 addresses and come back. Which order gives the shortest total distance?

Why this fitsEvery visiting order over 5 addresses is a permutation of 5. A used array records which addresses are already in the route, each step picks from the ones not yet placed, and reaching the bottom gives one complete route.

Anagrams and password variants

Which words can you spell by rearranging the letters of "listen"? Or: the password on a test account is some ordering of a few fragments, and you want to try every ordering.

Why this fitsRearranging letters is exactly permutation. When letters repeat you have to avoid producing the same result twice, which takes nothing more than sorting first and adding the rule "skip an equal value whose predecessor is unused".

Reach for it when you see:Order, arrangement, how many arrangements, each element used exactly once, n!, rearranging letters, the visiting order of a route.

02The core idea

Subsets ask, of each element, "in or out?"; permutations ask, of each position, "who goes here?". The first position has n choices, the second has n−1 left, and so on, which gives n! leaves. The decision tree is no longer binary: the number of branches at each level is the number of elements not yet used.

The most direct way to know who is still available is a used array. The loop at each level runs over every element, skips it when used[j] is true, and otherwise makes the choice (mark used, append to path), recurses into the next position, and undoes the choice (pop, unmark). The undo has to restore both things — miss one and the next branch sees a corrupted state, which is the single most common bug in permutation code.

The swap version does away with used and path altogether: position i is swapped in turn with every element from i onward, so the first i elements are the part already decided and the rest are the part still available. Swap back on the way out of the recursion. It saves an array, but it produces the permutations in a different order from the used version and is harder to adapt to duplicates.

The complexity is O(n!·n): n! permutations, each costing O(n) to copy. n = 10 is 3.6 million and n = 12 is already over 400 million, so full enumeration of permutations is only possible while n is tiny. For larger n the question is usually "which single arrangement is best", and the answer lies in DP (bitmask DP, for instance) or a greedy method. Duplicates are handled by sorting first: within one level, if nums[j] == nums[j-1] and used[j-1] is false, that value has already led at this position, so skip it.

03The algorithm

  1. 1Set up ans, path and used (all false). dfs() means "decide what goes in the next position".
  2. 2Base case: len(path) == n means every position is filled, so copy path into ans.
  3. 3Loop over every j: if used[j] is true, continue.
  4. 4Make the choice: used[j] = True, path.append(nums[j]), then recurse with dfs().
  5. 5Undo the choice: path.pop() and used[j] = False — both have to be restored — then try the next j.

04Interactive demo

The permutation tree for [1, 2, 3]. Each level picks from the numbers whose used flag is false, and the panel below shows the used array alongside the path. Notice that every undo restores the used array and the path together.

Startnums = [1, 2, 3] · each level picks from the unused numbers
∅112123131322212132323133131232321
nums
123
used
FFF
Current path
empty
Permutations collected (0/6)
none yet
Step 0/37A permutation is a decision about what goes in each position. Every level takes one of the numbers that has not been used yet and appends it to the path, while the used array records which numbers are already on the path.

05Code

The used-array version, the swap version, and the version that handles duplicates. All three share the skeleton "choose, recurse, undo"; they differ only in how they track which elements are still available.

# Permutations (LeetCode 46): the used array records who is already on the path
def permute(nums):
    ans = []
    path = []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):        # every position is filled
            ans.append(path[:])
            return
        for j in range(len(nums)):
            if used[j]:                   # already on the path, skip it
                continue
            used[j] = True                # make the choice
            path.append(nums[j])
            dfs()
            path.pop()                    # undo the choice
            used[j] = False

    dfs()
    return ans


# Swap version: swap position i with every element from i onward; no used array, no path
def permute_swap(nums):
    ans = []

    def dfs(i):
        if i == len(nums):
            ans.append(nums[:])
            return
        for j in range(i, len(nums)):
            nums[i], nums[j] = nums[j], nums[i]   # choose: put nums[j] at position i
            dfs(i + 1)
            nums[i], nums[j] = nums[j], nums[i]   # undo: swap it back

    dfs(0)
    return ans


# Permutations with duplicates (LeetCode 47): sort first, then equal values must be used in order
def permute_unique(nums):
    nums = sorted(nums)                   # sort into a new list, leaving the caller's input alone
    ans = []
    path = []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            ans.append(path[:])
            return
        for j in range(len(nums)):
            if used[j]:
                continue
            if j > 0 and nums[j] == nums[j - 1] and not used[j - 1]:
                continue                  # this value was already tried at this position
            used[j] = True
            path.append(nums[j])
            dfs()
            path.pop()
            used[j] = False

    dfs()
    return ans


if __name__ == "__main__":
    print(permute([1, 2, 3]))
    # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    print(permute_swap([1, 2, 3]))       # the same 6, but the last two come in a different order
    # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
    print(permute_unique([1, 1, 2]))
    # [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

06Practice

  • LeetCode 46PermutationsMedium
  • LeetCode 47Permutations II (sort, then test used[j-1])Medium
  • LeetCode 31Next Permutation (no backtracking: find the next one in lexicographic order)Medium
  • LeetCode 526Beautiful ArrangementMedium
  • LeetCode 60Permutation Sequence (compute the k-th directly with factorials)Hard
  • LeetCode 996Number of Squareful ArraysHard
PreviousSubsetsNextCombinations & Combination Sum