Introduction

Generating all permutations of a string means listing every possible ordering of its characters. The standard algorithmic approach is backtracking: fix one position, recursively permute the remaining positions, and then undo the choice so the next possibility can be explored.

Why The Problem Grows Fast

A string of length n has n! permutations if all characters are distinct.

Examples:

• '3! = 6'
• '4! = 24'
• '8! = 40320'

That growth means the real challenge is usually not how to write the recursion, but whether generating every permutation is practical for the input size.

Backtracking Approach

The usual recursive method swaps characters into the current position and recurses on the suffix.

1def permute(chars, start=0):
2    if start == len(chars):
3        print("".join(chars))
4        return
5
6    for i in range(start, len(chars)):
7        chars[start], chars[i] = chars[i], chars[start]
8        permute(chars, start + 1)
9        chars[start], chars[i] = chars[i], chars[start]
10
11
12permute(list("abc"))

This prints all six permutations of abc.

Why The Swap And Undo Matter

The recursive algorithm works because each level chooses which character should occupy the current index. After the recursive call finishes, the characters are swapped back so the next branch starts from the original state.

That undo step is what makes backtracking efficient and easy to reason about.

Handling Duplicate Characters

If the string contains repeated characters, naive recursion prints duplicate permutations.

For example, aab would generate repeated results unless you block duplicate choices at each recursion depth.

1def unique_permute(chars, start=0):
2    if start == len(chars):
3        print("".join(chars))
4        return
5
6    seen = set()
7    for i in range(start, len(chars)):
8        if chars[i] in seen:
9            continue
10        seen.add(chars[i])
11        chars[start], chars[i] = chars[i], chars[start]
12        unique_permute(chars, start + 1)
13        chars[start], chars[i] = chars[i], chars[start]
14
15
16unique_permute(list("aab"))

Now each distinct permutation appears once.

Library Alternative

If you only need the permutations rather than the exercise of implementing the algorithm, a standard library is often the better choice.

1from itertools import permutations
2
3for p in permutations("abc"):
4    print("".join(p))

This is concise and reliable, though it still has factorial output size because the combinatorics do not change.

Complexity

The time complexity is fundamentally tied to the number of outputs. For distinct characters, generating all permutations requires O(n * n!) time because there are n! outputs and each output has length n.

The space cost depends on the implementation, but the recursion depth is O(n) for the backtracking approach, not counting the space needed to store or print all results.

Common Pitfalls

The most common mistake is forgetting that the output size is factorial. Even a correct algorithm becomes unusable quickly for larger strings.

Another mistake is not swapping back after the recursive call, which corrupts the state for the remaining branches.

A third issue is ignoring duplicate characters and then wondering why the output contains repeated permutations.

Summary

• Backtracking is the standard way to generate all permutations of a string.
• The swap, recurse, and undo pattern is the core idea.
• Duplicate characters require extra logic to avoid repeated output.
• 'itertools.permutations is the simplest practical option in Python.'
• The main cost is factorial output size, so input length matters a lot.
• If you only need to count permutations, compute n! or the duplicate-adjusted formula instead of generating the strings explicitly.
• When memory matters, stream permutations one by one instead of storing the full result list.
• For interview problems, be explicit about whether duplicate characters should produce duplicate outputs or only unique permutations.