Print All Permutations of a String: Recursion, Backtracking, Heap Algorithm

Print All Permutations of a String: Recursion, Backtracking, and Iterative Heap’s Algorithm

Generating all permutations of a string is a foundational recursion / backtracking interview problem. It appears at FAANG, AI labs, and across the broader interview circuit because the standard solution exercises several core skills: recursion, in-place state mutation with restoration, and reasoning about exponential complexity. The base problem is simple but admits multiple equally valid implementations. This guide covers the standard recursive approach, the iterative Heap’s algorithm, the LeetCode-flavored permutation problem with duplicates, and the common pitfalls.

Problem Statement

Given a string s, return all distinct permutations of its characters.

Examples:

• s = "abc" → ["abc","acb","bac","bca","cab","cba"]
• s = "ab" → ["ab","ba"]
• s = "" → [""] (one permutation: empty)
• s = "aab" → ["aab","aba","baa"] (with duplicates handled)

The number of permutations is n! for distinct characters, smaller when duplicates are present.

Approach 1: Recursion with Swap (In-Place)

For each position in the array, swap each remaining character into that position and recurse on the rest. Restore the swap after recursion (backtracking).

def permutations(s: str) -> list[str]:
    """O(n!) time, O(n) recursion depth."""
    chars = list(s)
    result = []

    def backtrack(start: int):
        if start == len(chars):
            result.append("".join(chars))
            return
        seen = set()  # avoid duplicate permutations on duplicate chars
        for i in range(start, len(chars)):
            if chars[i] in seen:
                continue
            seen.add(chars[i])
            chars[start], chars[i] = chars[i], chars[start]
            backtrack(start + 1)
            chars[start], chars[i] = chars[i], chars[start]

    backtrack(0)
    return result


# Tests
print(permutations("abc"))  # 6 permutations
print(permutations("aab"))  # 3 distinct permutations
print(permutations(""))     # [""]

Complexity: O(n × n!) time (n! permutations, each takes O(n) to construct), O(n) recursion depth.

Why the seen set? When duplicates exist (e.g., “aab”), swapping in the first ‘a’ produces the same recursion subtree as swapping in the second ‘a’. The set prevents re-doing identical work.

Approach 2: Recursion with Used Array (LeetCode Style)

(LeetCode #46, #47) Standard “build up the result” pattern. Maintain a current permutation and a used-flag array; recurse to add each unused character.

def permute(nums: list[int]) -> list[list[int]]:
    """Standard LeetCode approach for arrays."""
    result = []
    current = []
    used = [False] * len(nums)

    def backtrack():
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            current.append(nums[i])
            used[i] = True
            backtrack()
            current.pop()
            used[i] = False

    backtrack()
    return result


# For duplicates (LeetCode #47):
def permute_unique(nums: list[int]) -> list[list[int]]:
    """Sort first, skip duplicates within a recursion level."""
    nums.sort()
    result = []
    current = []
    used = [False] * len(nums)

    def backtrack():
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            # Skip duplicates within this recursion level
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            current.append(nums[i])
            used[i] = True
            backtrack()
            current.pop()
            used[i] = False

    backtrack()
    return result

For duplicate handling, sort first; then skip an element if it equals the previous one and the previous one isn’t currently used. This canonicalizes the order in which duplicates can appear.

Approach 3: Iterative Heap’s Algorithm

Heap’s algorithm generates all permutations using minimal swap operations (one swap per permutation generated). Useful when you want to avoid recursion overhead.

def permutations_heap(s: str) -> list[str]:
    """Heap's algorithm — iterative, single-swap-per-perm."""
    chars = list(s)
    n = len(chars)
    result = ["".join(chars)]  # initial permutation
    c = [0] * n
    i = 0
    while i < n:
        if c[i] < i:
            if i % 2 == 0:
                chars[0], chars[i] = chars[i], chars[0]
            else:
                chars[c[i]], chars[i] = chars[i], chars[c[i]]
            result.append("".join(chars))
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return result

Trade-off: Same time complexity as recursive; constant factor is slightly better because of the single-swap property. Less intuitive code; rarely the expected interview answer. Mention if asked for non-recursive alternatives.

Approach 4: Built-In (Python itertools)

from itertools import permutations as iperm

def permutations_builtin(s: str) -> list[str]:
    return ["".join(p) for p in iperm(s)]


# Note: returns duplicates when input has duplicate characters
# Use set() to dedupe: list(set("".join(p) for p in iperm("aab")))

Don’t lead with this in interviews — they want to see the recursion. But mention as the production-equivalent.

Common Variations

Permutations of a list with constraints

“Generate all permutations such that no two adjacent elements are equal” or “such that the first element is smallest.” Add constraint checks in the backtracking loop.

Next permutation

(LeetCode #31) Given a permutation, return the next lexicographic permutation. Different problem; uses a clever in-place algorithm in O(n) time. Worth knowing as a related skill.

kth permutation

(LeetCode #60) Return the kth lexicographic permutation without generating all. Uses factorial decomposition: kth permutation can be computed directly by selecting elements based on factorials.

Permutation in string

(LeetCode #567) Check if any permutation of one string is a substring of another. Sliding window pattern; not a permutation generation problem.

String anagrams

Anagrams are permutations restricted to actual dictionary words. Generate all permutations then filter by dictionary lookup.

Common Mistakes

• Forgetting to backtrack the state. The swap must be undone after recursion, or subsequent iterations see corrupted state.
• Returning a reference to the current array instead of a copy. When appending to results, copy: result.append(current[:]) or result.append("".join(chars)). Otherwise all results point to the same (final-state) array.
• Generating duplicates without deduplication. “aab” naively gives 6 results, but only 3 are distinct. Either use a set, or use the sort + skip-duplicate-at-level pattern.
• Off-by-one in the recursion termination. The base case is start == len(chars), not start == len(chars) - 1. The latter misses the final position.
• Time complexity confusion. n! grows fast: 10! = 3.6M, 12! = 479M, 15! = 1.3T. Algorithms that generate all permutations are inherently exponential; for n > 10 or so, they’re impractical. Don’t claim “polynomial” complexity.

Frequently Asked Questions

See also: Longest Palindromic Substring • Remove a Character from a String • Two Sum: Find a Pair in an Array

function permute(str) {
    const result = [];
    const arr = str.split(''); // Convert to array for swapping

    function backtrack(start) {
        // Base case: reached end of string
        if (start === arr.length - 1) {
            result.push(arr.join(''));
            return;
        }

        // Try each character in remaining positions
        for (let i = start; i < arr.length; i++) {
            // Swap character to current position
            [arr[start], arr[i]] = [arr[i], arr[start]];

            // Recurse on remaining positions
            backtrack(start + 1);

            // Backtrack: swap back
            [arr[start], arr[i]] = [arr[i], arr[start]];
        }
    }

    backtrack(0);
    return result;
}

// Test
console.log(permute("ABC"));
// Output: ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]

console.log(permute("AB"));
// Output: ["AB", "BA"]

function permuteBuilding(str) {
    const result = [];

    function backtrack(current, remaining) {
        // Base case: used all characters
        if (remaining.length === 0) {
            result.push(current);
            return;
        }

        // Try each remaining character next
        for (let i = 0; i < remaining.length; i++) {
            const char = remaining[i];
            const newRemaining = remaining.slice(0, i) + remaining.slice(i + 1);
            backtrack(current + char, newRemaining);
        }
    }

    backtrack('', str);
    return result;
}

console.log(permuteBuilding("ABC"));
// Output: ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]

function permuteUnique(str) {
    const result = [];
    const arr = str.split('').sort(); // Sort to group duplicates
    const used = new Array(arr.length).fill(false);

    function backtrack(current) {
        if (current.length === arr.length) {
            result.push(current.join(''));
            return;
        }

        for (let i = 0; i < arr.length; i++) {
            // Skip if used or duplicate of previous unused char
            if (used[i] || (i > 0 && arr[i] === arr[i-1] && !used[i-1])) {
                continue;
            }

            used[i] = true;
            current.push(arr[i]);
            backtrack(current);
            current.pop();
            used[i] = false;
        }
    }

    backtrack([]);
    return result;
}

console.log(permuteUnique("AAB"));
// Output: ["AAB", "ABA", "BAA"]