Introduction

If the goal is to generate every permutation of a string, there is no magic algorithm that avoids factorial growth. The output itself has size n!, so any complete solution must do at least that much work. The real question is not how to beat factorial time. It is which method gives the cleanest implementation, lowest overhead, or correct handling of duplicate characters.

The Lower Bound Comes First

For a string of length n, the number of permutations is n!.

That means:

• '3 characters give 6 permutations'
• '5 characters give 120'
• '10 characters give 3,628,800'

So the best method depends on whether you need:

• all permutations eagerly
• one permutation at a time
• unique permutations only
• low memory overhead

No algorithm can make "generate them all" fundamentally cheap.

Classic Backtracking

Backtracking is the standard general-purpose solution. It builds one permutation incrementally, marks used characters, and backtracks.

1def permutations(s):
2    chars = list(s)
3    used = [False] * len(chars)
4    path = []
5    result = []
6
7    def backtrack():
8        if len(path) == len(chars):
9            result.append("".join(path))
10            return
11
12        for i, ch in enumerate(chars):
13            if used[i]:
14                continue
15            used[i] = True
16            path.append(ch)
17            backtrack()
18            path.pop()
19            used[i] = False
20
21    backtrack()
22    return result
23
24
25print(permutations("abc"))

This is easy to understand and works in most languages.

In-Place Swapping

If you want lower auxiliary memory, swap characters in place instead of tracking a used array.

1def permute_in_place(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_in_place(chars, start + 1)
9        chars[start], chars[i] = chars[i], chars[start]
10
11
12permute_in_place(list("abc"))

This is a strong answer when you need recursion with minimal extra state.

Use Lazy Iteration When Possible

If you do not need all permutations stored at once, generate them lazily.

Python's itertools.permutations is excellent for this.

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

This is usually the best practical answer in Python because:

• it is battle-tested
• it avoids writing your own recursion
• it yields results lazily

If your language has a standard combinatorics library, prefer that unless you need custom control.

Duplicate Characters Change The Story

If the string contains repeated characters, naive permutation code generates duplicates.

For example, aab has only 3 unique permutations:

• 'aab'
• 'aba'
• 'baa'

A duplicate-aware backtracking approach sorts the characters and skips equivalent choices.

1def unique_permutations(s):
2    chars = sorted(s)
3    used = [False] * len(chars)
4    path = []
5    result = []
6
7    def backtrack():
8        if len(path) == len(chars):
9            result.append("".join(path))
10            return
11
12        for i in range(len(chars)):
13            if used[i]:
14                continue
15            if i > 0 and chars[i] == chars[i - 1] and not used[i - 1]:
16                continue
17
18            used[i] = True
19            path.append(chars[i])
20            backtrack()
21            path.pop()
22            used[i] = False
23
24    backtrack()
25    return result
26
27
28print(unique_permutations("aab"))

This is often a more meaningful optimization than arguing about minor overhead differences between recursion styles.

So What Is The "Better" Method

A practical answer is:

• use a standard library iterator when available
• use backtracking when you need custom logic
• use duplicate-aware generation when the string has repeated characters
• use lazy generation when you do not need to store all results

Those are genuine improvements in ergonomics and memory behavior, even though the factorial output size remains unavoidable.

Common Pitfalls

A common mistake is asking for a "better" algorithm without considering the factorial output size. If you must enumerate all permutations, exponential growth is not avoidable.

Another issue is generating all permutations into memory when you only need to stream them one at a time. A lazy iterator is often much better.

Developers also often forget duplicate handling. Naive algorithms work fine on abc but waste time and produce repeated answers on inputs such as aab.

Finally, do not optimize the recursion style before clarifying the actual goal. Unique generation, lazy iteration, and pruning constraints matter far more than micro-optimizing function calls.

Summary

• No complete permutation generator can avoid factorial growth because the output itself is factorial in size.
• Backtracking is the standard custom solution.
• In-place swapping reduces auxiliary state.
• Library iterators such as itertools.permutations are usually the best practical option when available.
• Handling duplicate characters and using lazy generation are often the most meaningful real improvements.