Introduction

Recursively generating all permutations of an array is a standard backtracking problem. The core idea is to fix one position at a time, try every possible element in that position, and recurse on the remaining positions.

This technique is valuable because it teaches two important ideas at once: recursion and backtracking. It also makes the growth in output size obvious, because an array of length n has n! permutations.

The Swap-and-Backtrack Approach

One classic recursive solution swaps elements in place. At recursion level start, you decide which element belongs at index start, swap it into position, recurse, and then swap back to restore the original state.

1def permutations(arr, start=0):
2    if start == len(arr):
3        print(arr[:])
4        return
5
6    for i in range(start, len(arr)):
7        arr[start], arr[i] = arr[i], arr[start]
8        permutations(arr, start + 1)
9        arr[start], arr[i] = arr[i], arr[start]
10
11
12permutations([1, 2, 3])

1[1, 2, 3]
2[1, 3, 2]
3[2, 1, 3]
4[2, 3, 1]
5[3, 2, 1]
6[3, 1, 2]

The second swap is the backtracking step. Without it, later recursive branches would start from a mutated array and the result would be wrong.

How the Recursion Tree Works

At the top level, every element gets a chance to occupy the first position. For each such choice, every remaining element gets a chance to occupy the second position, and so on.

For [1, 2, 3], the recursion conceptually explores:

• fix 1, then permute [2, 3]
• fix 2, then permute [1, 3]
• fix 3, then permute [1, 2]

The base case happens when start == len(arr). At that moment, every position has been fixed, so the current arrangement is one complete permutation.

Return a List Instead of Printing

Printing is useful for learning, but most real programs need to return the permutations.

1def permutations_list(arr, start=0, result=None):
2    if result is None:
3        result = []
4
5    if start == len(arr):
6        result.append(arr[:])
7        return result
8
9    for i in range(start, len(arr)):
10        arr[start], arr[i] = arr[i], arr[start]
11        permutations_list(arr, start + 1, result)
12        arr[start], arr[i] = arr[i], arr[start]
13
14    return result
15
16
17print(permutations_list(["a", "b", "c"]))

This collects all permutations into memory. That is fine for small arrays, but remember that the total result count is n!, so memory usage grows quickly.

A Generator Version Is Often Better

If you want to iterate over permutations lazily, use yield instead of building one big list.

1def permutations_generator(arr, start=0):
2    if start == len(arr):
3        yield arr[:]
4        return
5
6    for i in range(start, len(arr)):
7        arr[start], arr[i] = arr[i], arr[start]
8        yield from permutations_generator(arr, start + 1)
9        arr[start], arr[i] = arr[i], arr[start]
10
11
12for perm in permutations_generator([1, 2, 3]):
13    print(perm)

The generator version is often the most practical when you want to stream results into another algorithm rather than materialize them all at once.

What About Duplicate Values?

If the array contains repeated values, the simple swap approach will produce duplicate permutations. For example, [1, 1, 2] generates repeated outputs unless you skip repeated choices at each recursion depth.

One common approach is to track which values have already been used for the current start position.

1def unique_permutations(arr, start=0):
2    if start == len(arr):
3        yield arr[:]
4        return
5
6    used = set()
7    for i in range(start, len(arr)):
8        if arr[i] in used:
9            continue
10        used.add(arr[i])
11
12        arr[start], arr[i] = arr[i], arr[start]
13        yield from unique_permutations(arr, start + 1)
14        arr[start], arr[i] = arr[i], arr[start]

That small addition prevents duplicate branches caused by identical values.

Complexity Matters

Any algorithm that generates every permutation must do at least n! work because the output itself contains n! items. The recursive overhead is usually not the real problem; the combinatorial explosion is.

That means recursive permutation generation is appropriate only when n is small or when you can stop early after finding what you need.

Common Pitfalls

The most common bug is forgetting to swap back after the recursive call. That breaks the backtracking logic and corrupts later branches.

Another issue is appending arr directly instead of arr[:] when saving a result. Without copying, every saved permutation points to the same list object, and all stored results end up identical.

People also underestimate how quickly n! grows. Even length 10 means 3,628,800 permutations, which is far too many for many practical tasks.

Finally, if duplicates are possible in the input, you need extra logic to avoid duplicate outputs.

Summary

• Recursive permutation generation usually uses swap-based backtracking.
• Fix one position, recurse on the rest, then swap back to restore state.
• Copy the array when recording a completed permutation.
• Use a generator when you want lazy iteration instead of storing every result.
• Be aware that the total number of permutations is n!, so the method only scales to small inputs.