A permutation of a string is any reordering of its characters. For a string of length n there are n! (n factorial) permutations, so even a short 4-5 character string already produces dozens of results. Generating them all is a classic interview question because it's a clean introduction to backtracking — a technique that shows up again and again in harder problems like N-Queens or Sudoku solvers.

The idea behind backtracking here: at each position, try placing every character that hasn't been used yet, recurse into the next position, and when you run out of characters you've built one full permutation. After exploring a choice, "backtrack" by un-choosing it so the next option at that position can be tried.

Python Program to Find All Permutations of a String (Backtracking)

def permutations(s):
    results = []

    def backtrack(path, remaining):
        if not remaining:
            results.append(path)
            return
        for i in range(len(remaining)):
            # choose remaining[i], recurse on what's left, then move on
            backtrack(path + remaining[i], remaining[:i] + remaining[i + 1:])

    backtrack("", s)
    return results


for p in permutations("abc"):
    print(p)

Output:

abc
acb
bac
bca
cab
cba

Handling Duplicate Characters

If the string has repeated characters (like "aab"), the backtracking version above will produce duplicate permutations, since it treats both 'a's as distinct even though they look identical. The simplest fix is collecting results into a set before printing:

print(sorted(set(permutations("aab"))))

Output:

['aab', 'aba', 'baa']

For production code, you rarely need to write this by hand — Python's standard library already has it covered with itertools.permutations("abc"), which returns an iterator of tuples lazily rather than building the whole list in memory at once. Writing the recursive version yourself is still worth knowing, though, since the same backtracking skeleton — choose, recurse, un-choose — is what you'll reuse for combinations, subsets, and board-based puzzles. The time complexity is O(n! × n) since there are n! permutations and building each one takes O(n).