Loading…

mediumBacktrackingSometimes asked

Permutations of Strings

Q: How do you solve Permutations of Strings using the Brute Force — Generate All, Then Sort and Dedup approach?

When to use it: Mention as the obvious baseline, then improve to emitting in order directly. The most direct route: enumerate first, tidy up after. **Enumerate.** Run the textbook permutation backtracking — `used[]` array, choose/explore/un-choose, record at full length — without worrying about order or repeats. This yields all n! orderings (with duplicates if characters repeat). **Dedup.** Insert each permutation into a `set` so identical strings (from swapping two equal characters) collapse to one. **Sort.** The set is unordered, so sort the distinct permutations lexicographically before returning. **Why it's only a baseline.** It's correct and easy to reason about, but it pays twice: it generates duplicate work for repeated characters (then throws it away), and it sorts n! strings at the end. The optimal version sorts the *characters once* up front so the search emits permutations already distinct and already sorted — turning an O(n·n!·log n!) finish into linear collection. Lead with this to show you can get a correct answer, then refine. Time complexity: O(n · n! · log(n!)). Space complexity: O(n · n!).

Backtracking · 12 of 13 · 10 min

Given a string s, generate all permutations of its characters and return them in lexicographically sorted (dictionary) order.

If the string contains repeated characters, each distinct permutation must appear exactly once.

For example, s = "ab" returns ["ab", "ba"], and s = "aba" returns ["aab", "aba", "baa"].

In plain English

Produce every distinct ordering of the characters, sorted as a dictionary would. Because permutations care about order, there's no start index — every position can take any unused character. Sorting the characters up front means the backtracking explores them smallest-first, so results come out already sorted. Repeated characters would otherwise yield duplicate permutations; a same-level skip collapses them so each distinct arrangement is emitted once.

Examples

Example 1

Input: s = "ab"
Output: ["ab", "ba"]
Note: Two permutations of distinct characters, already in sorted order.

Example 2

Input: s = "aba"
Output: ["aab", "aba", "baa"]
Note: Three distinct permutations (not 3! = 6) because the two 'a's are identical — the dedup skip collapses the repeats.

Example 3

Input: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"]
Note: All 3! = 6 permutations in dictionary order, produced directly by iterating the sorted characters a, b, c.

Constraints

1 ≤ s.length ≤ 10
s consists of printable characters (commonly lowercase letters)
The string may contain repeated characters
Output must be in lexicographic order with no duplicate permutations
Number of distinct permutations ≤ n! (fewer when characters repeat)

Clarifying questions4First question: Should the output be sorted, or is any order acceptable?Explore questions

Q1.Should the output be sorted, or is any order acceptable?
Lexicographically sorted. We achieve that by sorting the characters first and iterating them in order — no need to sort the final list.
Q2.Can the string contain duplicate characters?
Yes. We must emit each distinct permutation once, so a same-level duplicate skip (`chars[i]==chars[i-1] && !used[i-1]`) is required.
Q3.Does every permutation use all characters?
Yes — a permutation is a full rearrangement, so each result has length n. We record only at full-length leaves.
Q4.How large can the string get?
Up to length 10, so at most 10! = 3,628,800 permutations — large but enumerable. The small bound confirms full enumeration is intended.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Generate **all permutations of a string in lexicographic (dictionary) order**. Sort the characters first, then backtrack with a `used[]` array: at each position loop the sorted characters left to right, skip used ones, and — to handle repeated letters — skip a duplicate character when its identical predecessor hasn't been used at this level. Choosing in sorted order with that dedup rule emits permutations already sorted, so no final sort is needed. There are up to n! permutations, so the cost is O(n · n!).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you produce permutations in lexicographic order by sorting first (not by sorting the result afterwards), use the used[] template correctly, and handle repeated characters with the same-level skip.

Where candidates slip

Generating all permutations then sorting (works but signals you didn't see the cleaner emission), forgetting the duplicate-skip so repeated letters produce duplicate permutations, or omitting `used[i] = false` on backtrack.

How to stand out

Explain why iterating sorted characters yields lexicographic output directly, articulate the `chars[i]==chars[i-1] && !used[i-1]` dedup precisely, and note that for just the next permutation you'd switch to the O(n) next_permutation algorithm.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Generate All, Then Sort and Dedup	`O(n · n! · log(n!))`	`O(n · n!)`	Mention as the obvious baseline, then improve to emitting in order directly.	Read
2	Sort + Backtracking with Duplicate Skip (Optimal)Optimal	`O(n · n!)`	`O(n)`	The clean answer. Phrase it as 'sort the characters so the search visits them in order, then skip same-level duplicates'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewPermutations of a stringAll of them or just the next?Just nextAllExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Generate All, Then Sort and Dedup

TimeO(n · n! · log(n!))SpaceO(n · n!)

Mention as the obvious baseline, then improve to emitting in order directly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Generate every permutation with the standard used[] backtracking, ignoring order and duplicates for now.

2Hint 2Explore hint

Collect them into a set to drop duplicate permutations that arise from repeated characters.

3Hint 3Explore hint

Sort the resulting collection lexicographically and return it.

A · Core idea

The most direct route: enumerate first, tidy up after.

Enumerate. Run the textbook permutation backtracking — used[] array, choose/explore/un-choose, record at full length — without worrying about order or repeats. This yields all n! orderings (with duplicates if characters repeat).

Dedup. Insert each permutation into a set so identical strings (from swapping two equal characters) collapse to one.

Sort. The set is unordered, so sort the distinct permutations lexicographically before returning.

Why it's only a baseline. It's correct and easy to reason about, but it pays twice: it generates duplicate work for repeated characters (then throws it away), and it sorts n! strings at the end. The optimal version sorts the characters once up front so the search emits permutations already distinct and already sorted — turning an O(n·n!·log n!) finish into linear collection. Lead with this to show you can get a correct answer, then refine.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba"

Interactive diagram

Generate, dedup, sort

generate

Active call / nodeSupporting contextReturned stateNot active

Duplicates from repeated letters are collapsed by the set, then sorted at the end.

Final result["aab", "aba", "baa"]

C · Code with teaching comments

Reference implementation previewimport java.util.*; public List<String> permutations(String s) { char[] chars = s.toCharArray(); boolean[] used = new boolean[chars.length];Explore the full code

solution.javaJava

Brute Force — Generate All, Then Sort and Dedup — reference

3 teaching notes

1
import java.util.*;
2
 
3
public List<String> permutations(String s) {
4
    char[] chars = s.toCharArray();
5
    boolean[] used = new boolean[chars.length];
6
    // A TreeSet both removes duplicates and yields sorted order on iteration.
7
    Set<String> seen = new TreeSet<>();   // TreeSet keeps them sorted + deduped
8
    backtrack(chars, used, new StringBuilder(), seen);
9
    return new ArrayList<>(seen);
10
}
11
 
12
private void backtrack(char[] chars, boolean[] used, StringBuilder path, Set<String> seen) {
13
    // Record only full-length permutations.
14
    if (path.length() == chars.length) {
15
        seen.add(path.toString());
16
        return;
17
    }
18
    for (int i = 0; i < chars.length; i++) {
19
        if (used[i]) continue;
20
        used[i] = true;
21
        path.append(chars[i]);
22
        backtrack(chars, used, path, seen);
23
        path.deleteCharAt(path.length() - 1);
24
        // Restore the flag after recursion — the standard un-choose.
25
        used[i] = false;
26
    }
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n · n! · log(n!)) timeO(n · n!) spaceOpen the invariant and proofExplore the proof

Sorting the output is the lazy way to get lexicographic order; sorting the input is the smart way. Whenever 'sorted results' is required from an enumeration, ask whether ordering the choices up front removes the post-sort entirely.

ComplexityO(n · n! · log(n!)) time, O(n · n!) space — Generating permutations is O(n · n!). Deduping via a set is O(n) per permutation. The final sort of up to n! strings of length n costs O(n · n! · log(n!)). Storage holds all permutations → O(n · n!).

E · Edge cases and pitfalls3Generating n! permutations even when many are identical — wasted work for repeated characters.Explore edge cases

Pitfalls

Generating n! permutations even when many are identical — wasted work for repeated characters.
Forgetting to sort when using a plain HashSet — order would be arbitrary.
Omitting `used[i] = false` — drops most permutations.

03.2

Approach 2 of 2 · Optimal

Sort + Backtracking with Duplicate Skip (Optimal)

TimeO(n · n!)SpaceO(n)

The clean answer. Phrase it as 'sort the characters so the search visits them in order, then skip same-level duplicates'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Sort the characters first. Iterating them smallest-first at every position makes the permutations come out in lexicographic order with no post-sort.

2Hint 2Explore hint

Use a `used[]` array (no start index — order matters). At each level loop i from 0, skip used[i].

3Hint 3Explore hint

To avoid duplicate permutations from repeated characters, skip a character equal to its predecessor when that predecessor isn't currently used: `chars[i]==chars[i-1] && !used[i-1] → continue`. Record at a full-length leaf.

A · Core idea

Two ideas combine: emit in order, and emit each distinct permutation once.

Sort so output is sorted. Sort the characters before searching. At every position we loop the characters from index 0 upward, so we always try the smallest available character first. Doing that at every level means the very first complete permutation is the smallest, the next is the next-smallest, and so on — the results stream out in dictionary order. No final sort is needed.

used[] because order matters. Permutations are an 'order matters' problem, so there is no start index: position 0 can be any character, position 1 any of the rest. A boolean used[] tracks which characters are already in the current path; we continue past used ones so each character appears once per permutation.

The duplicate-skip line. With repeated characters, two identical letters at different indices would generate the same permutation twice. The fix is one line: if (i > 0 && chars[i] == chars[i-1] && !used[i-1]) continue;. Read it as: don't start a branch with this character if an identical character just before it is still available and unused at this level. That forces equal characters to be consumed in their fixed left-to-right order, so each distinct arrangement is produced exactly once. The !used[i-1] part is crucial — if the predecessor is used (it's part of the current path), then this chars[i] is a legitimately different position to fill, not a duplicate sibling.

Symmetric undo. Choosing does used[i] = true and path.append; un-choosing must undo both with path.pop() and used[i] = false. Forget the second and the character stays marked forever, dropping permutations.

Record at full length. A permutation uses all n characters, so we snapshot the path only when len(path) == n.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba" (sorted → a, a, b at indices 0,1,2)

Interactive diagram

Recursion tree for sorted a,a,b

pos0 try i=0 'a'

Active call / nodeSupporting contextReturned stateNot active

The crossed branch is the duplicate 'a' at position 0, skipped by the dedup rule. Leaves are emitted in sorted order.

Final result["aab", "aba", "baa"]

C · Code with teaching comments

solution.javaJava

Sort + Backtracking with Duplicate Skip (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
public List<String> permutations(String s) {
4
    char[] chars = s.toCharArray();
5
    // Sorting the characters makes the in-order traversal produce sorted permutations
6
    // directly.
7
    Arrays.sort(chars);                       // sort → lexicographic emission
8
    boolean[] used = new boolean[chars.length];
9
    List<String> results = new ArrayList<>();
10
    backtrack(chars, used, new StringBuilder(), results);
11
    return results;
12
}
13
 
14
private void backtrack(char[] chars, boolean[] used,
15
                       StringBuilder path, List<String> results) {
16
    // A permutation uses all characters; record only at full length.
17
    if (path.length() == chars.length) {
18
        results.add(path.toString());         // full-length leaf → record
19
        return;
20
    }
21
    for (int i = 0; i < chars.length; i++) {
22
        if (used[i]) continue;                 // already placed
23
        // Skip an equal sibling whose identical predecessor is still unused — collapses
24
        // duplicate permutations.
25
        if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;  // dedup
26
        // Mark the character placed so deeper levels skip it.
27
        used[i] = true;                        // choose
28
        path.append(chars[i]);
29
        backtrack(chars, used, path, results); // explore
30
        // Pop the character; the next line unmarks it — both must be undone.
31
        path.deleteCharAt(path.length() - 1);  // un-choose: restore BOTH
32
        used[i] = false;
33
    }
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(n · n!) timeO(n) spaceOpen the invariant and proofExplore the proof

Lexicographic order is bought by sorting the choices, not the results. And the one-line same-level duplicate skip — 'skip an equal sibling whose twin is still unused' — is the single most reused trick across Permutations II, Subsets II, and Combination Sum II. Learn it once, apply it everywhere duplicates must collapse.

ComplexityO(n · n!) time, O(n) space — Sorting is O(n log n), dominated by the enumeration. There are at most n! distinct permutations, each costing O(n) to build/emit → O(n · n!). Extra space is the recursion depth (n), the path (n), and used[] (n) → O(n) beyond the output.

E · Edge cases and pitfalls6s = "a" — One character → one permutation. Records ["a"] at the single full-length leaf.Explore edge cases

Edge cases handled

s = "a"One character → one permutation. Records ["a"] at the single full-length leaf.
s = "aa"The dedup skip blocks the second branch → only ["aa"], not ["aa", "aa"].
s = "ba"Sorted to a, b first, so output is ["ab", "ba"] in lexicographic order despite the input order.

Pitfalls

Sorting the result instead of the input — works but wastes an O(n·n!·log n!) sort.
Dropping the `!used[i-1]` condition in the dedup — over-skips and loses valid permutations.
Forgetting `used[i] = false` on backtrack — leaves characters marked and loses permutations.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; public List<String> permutations(String s) { char[] chars = s.toCharArray(); Arrays.sort(chars); // sort → lexicographic emissionExplore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

public List<String> permutations(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);                       // sort → lexicographic emission
    boolean[] used = new boolean[chars.length];
    List<String> results = new ArrayList<>();
    backtrack(chars, used, new StringBuilder(), results);
    return results;
}

private void backtrack(char[] chars, boolean[] used,
                       StringBuilder path, List<String> results) {
    if (path.length() == chars.length) {
        results.add(path.toString());         // full-length leaf → record
        return;
    }
    for (int i = 0; i < chars.length; i++) {
        if (used[i]) continue;                 // already placed
        if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;  // dedup
        used[i] = true;                        // choose
        path.append(chars[i]);
        backtrack(chars, used, path, results); // explore
        path.deleteCharAt(path.length() - 1);  // un-choose: restore BOTH
        used[i] = false;
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing duplicate skip

With repeated characters, two identical letters generate the same permutation twice. The same-level skip collapses them so each distinct permutation appears once.

Explore the code comparison

Don't write this

for i in range(n):
    if used[i]:
        continue
    # no dedup → 'aa' produces ['aa', 'aa']
    used[i] = True; path.append(chars[i])

Write this instead

for i in range(n):
    if used[i]:
        continue
    if i > 0 and chars[i] == chars[i-1] and not used[i-1]:
        continue                       # dedup
    used[i] = True; path.append(chars[i])

Sorting the output, not the input

Sorting n! results at the end is far costlier than sorting the n characters once. Iterating sorted characters emits permutations already in order.

Explore the code comparison

Don't write this

List<String> all = generateAll(s);
Collections.sort(all);   // O(n · n! · log n!)
return all;

Write this instead

char[] chars = s.toCharArray();
Arrays.sort(chars);      // O(n log n), once
// backtrack emits in lexicographic order

Asymmetric backtrack

Choosing sets used[i] = true and appends; if un-choose only pops, the character stays marked for every sibling branch and most permutations vanish.

Explore the code comparison

Don't write this

used[i] = True; path.append(chars[i])
backtrack()
path.pop()                # used[i] never reset!

Write this instead

used[i] = True; path.append(chars[i])
backtrack()
path.pop(); used[i] = False   # restore BOTH

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort + backtracking with used[] and same-level duplicate skip (lexicographic emission)

Code pattern to memorize

chars = sorted(s)

def backtrack(path):
    if len(path) == n: emit(''.join(path)); return
    for i in range(n):
        if used[i]: continue
        if i > 0 and chars[i] == chars[i-1] and not used[i-1]: continue  # dedup
        used[i] = True; path.append(chars[i])
        backtrack(path)
        path.pop(); used[i] = False

Rules to remember

1Sort the characters first — iterating them in order is what makes the output lexicographic without a post-sort.
2Use a used[] array (no start index) so every position can draw any not-yet-placed character — order matters in permutations.
3Dedup repeated letters with if chars[i] == chars[i-1] and not used[i-1]: continue — skips identical siblings at the same level so each distinct permutation appears once.
4Restore both path.pop() and used[i] = False on backtrack — asymmetric undo is the classic bug.
5Emit a copy/join at a full-length leaf only; partial paths aren't permutations.

Use this pattern when

All arrangements of a string/array, especially required in sorted order
Lexicographic enumeration where a stream of permutations is consumed in order
Input may contain repeated characters and duplicates must be collapsed
Anagram listing, password/keyspace enumeration of small length

Choose another pattern when

Only the NEXT permutation is needed → use next_permutation (O(n)), not full enumeration
Only the COUNT of distinct permutations → it's n! / (product of duplicate factorials), no enumeration
All characters distinct and order of output irrelevant → plain permutations, skip sort + dedup
n is large (> ~10) → n! is infeasible to enumerate

Interview takeaway

Lexicographic string permutations = sort the characters so the backtracking visits them in order, then apply the standard used[] permutation template with one extra line — the same-level duplicate skip. Master the dedup rule here and Permutations II, Subsets II, and Combination Sum II reuse it verbatim.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternLexicographic permutation enumeration: sort the choices so the backtracking emits results in order, use a used[] set because order matters, and apply the one-line same-level duplicate skip to collapse repeats. The dedup rule is shared with Permutations II, Subsets II, and Combination Sum II.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Permutations II
Coming soon
Permutations of an array with duplicates — exactly this sort + same-level skip on integers.
Next Permutation
Coming soon
Only the single next ordering in O(n) — find the pivot, swap, reverse the suffix. No enumeration.
Subsets II
Coming soon
Same duplicate-skip idea applied to subsets instead of permutations.

Same pattern

←

Crossword Puzzle

Continue · Next problem

The Power Sum

mediumBacktrackingSometimes asked

Permutations of Strings

Backtracking · 12 of 13 · 10 min

Given a string s, generate all permutations of its characters and return them in lexicographically sorted (dictionary) order.

If the string contains repeated characters, each distinct permutation must appear exactly once.

For example, s = "ab" returns ["ab", "ba"], and s = "aba" returns ["aab", "aba", "baa"].

In plain English

Examples

Example 1

Input: s = "ab"
Output: ["ab", "ba"]
Note: Two permutations of distinct characters, already in sorted order.

Example 2

Input: s = "aba"
Output: ["aab", "aba", "baa"]
Note: Three distinct permutations (not 3! = 6) because the two 'a's are identical — the dedup skip collapses the repeats.

Example 3

Input: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"]
Note: All 3! = 6 permutations in dictionary order, produced directly by iterating the sorted characters a, b, c.

Constraints

1 ≤ s.length ≤ 10
s consists of printable characters (commonly lowercase letters)
The string may contain repeated characters
Output must be in lexicographic order with no duplicate permutations
Number of distinct permutations ≤ n! (fewer when characters repeat)

Clarifying questions4First question: Should the output be sorted, or is any order acceptable?Explore questions

Q1.Should the output be sorted, or is any order acceptable?
Lexicographically sorted. We achieve that by sorting the characters first and iterating them in order — no need to sort the final list.
Q2.Can the string contain duplicate characters?
Yes. We must emit each distinct permutation once, so a same-level duplicate skip (`chars[i]==chars[i-1] && !used[i-1]`) is required.
Q3.Does every permutation use all characters?
Yes — a permutation is a full rearrangement, so each result has length n. We record only at full-length leaves.
Q4.How large can the string get?
Up to length 10, so at most 10! = 3,628,800 permutations — large but enumerable. The small bound confirms full enumeration is intended.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Generate All, Then Sort and Dedup	`O(n · n! · log(n!))`	`O(n · n!)`	Mention as the obvious baseline, then improve to emitting in order directly.	Read
2	Sort + Backtracking with Duplicate Skip (Optimal)Optimal	`O(n · n!)`	`O(n)`	The clean answer. Phrase it as 'sort the characters so the search visits them in order, then skip same-level duplicates'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Generate All, Then Sort and Dedup

TimeO(n · n! · log(n!))SpaceO(n · n!)

Mention as the obvious baseline, then improve to emitting in order directly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Generate every permutation with the standard used[] backtracking, ignoring order and duplicates for now.

2Hint 2Explore hint

Collect them into a set to drop duplicate permutations that arise from repeated characters.

3Hint 3Explore hint

Sort the resulting collection lexicographically and return it.

A · Core idea

The most direct route: enumerate first, tidy up after.

Dedup. Insert each permutation into a set so identical strings (from swapping two equal characters) collapse to one.

Sort. The set is unordered, so sort the distinct permutations lexicographically before returning.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba"

Interactive diagram

Generate, dedup, sort

generate

Active call / nodeSupporting contextReturned stateNot active

Duplicates from repeated letters are collapsed by the set, then sorted at the end.

Final result["aab", "aba", "baa"]

C · Code with teaching comments

Reference implementation previewimport java.util.*; public List<String> permutations(String s) { char[] chars = s.toCharArray(); boolean[] used = new boolean[chars.length];Explore the full code

solution.javaJava

Brute Force — Generate All, Then Sort and Dedup — reference

3 teaching notes

1
import java.util.*;
2
 
3
public List<String> permutations(String s) {
4
    char[] chars = s.toCharArray();
5
    boolean[] used = new boolean[chars.length];
6
    // A TreeSet both removes duplicates and yields sorted order on iteration.
7
    Set<String> seen = new TreeSet<>();   // TreeSet keeps them sorted + deduped
8
    backtrack(chars, used, new StringBuilder(), seen);
9
    return new ArrayList<>(seen);
10
}
11
 
12
private void backtrack(char[] chars, boolean[] used, StringBuilder path, Set<String> seen) {
13
    // Record only full-length permutations.
14
    if (path.length() == chars.length) {
15
        seen.add(path.toString());
16
        return;
17
    }
18
    for (int i = 0; i < chars.length; i++) {
19
        if (used[i]) continue;
20
        used[i] = true;
21
        path.append(chars[i]);
22
        backtrack(chars, used, path, seen);
23
        path.deleteCharAt(path.length() - 1);
24
        // Restore the flag after recursion — the standard un-choose.
25
        used[i] = false;
26
    }
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n · n! · log(n!)) timeO(n · n!) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Generating n! permutations even when many are identical — wasted work for repeated characters.Explore edge cases

Pitfalls

Generating n! permutations even when many are identical — wasted work for repeated characters.
Forgetting to sort when using a plain HashSet — order would be arbitrary.
Omitting `used[i] = false` — drops most permutations.

03.2

Approach 2 of 2 · Optimal

Sort + Backtracking with Duplicate Skip (Optimal)

TimeO(n · n!)SpaceO(n)

The clean answer. Phrase it as 'sort the characters so the search visits them in order, then skip same-level duplicates'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Sort the characters first. Iterating them smallest-first at every position makes the permutations come out in lexicographic order with no post-sort.

2Hint 2Explore hint

Use a `used[]` array (no start index — order matters). At each level loop i from 0, skip used[i].

3Hint 3Explore hint

A · Core idea

Two ideas combine: emit in order, and emit each distinct permutation once.

Record at full length. A permutation uses all n characters, so we snapshot the path only when len(path) == n.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aba" (sorted → a, a, b at indices 0,1,2)

Interactive diagram

Recursion tree for sorted a,a,b

pos0 try i=0 'a'

Active call / nodeSupporting contextReturned stateNot active

The crossed branch is the duplicate 'a' at position 0, skipped by the dedup rule. Leaves are emitted in sorted order.

Final result["aab", "aba", "baa"]

C · Code with teaching comments

solution.javaJava

Sort + Backtracking with Duplicate Skip (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
public List<String> permutations(String s) {
4
    char[] chars = s.toCharArray();
5
    // Sorting the characters makes the in-order traversal produce sorted permutations
6
    // directly.
7
    Arrays.sort(chars);                       // sort → lexicographic emission
8
    boolean[] used = new boolean[chars.length];
9
    List<String> results = new ArrayList<>();
10
    backtrack(chars, used, new StringBuilder(), results);
11
    return results;
12
}
13
 
14
private void backtrack(char[] chars, boolean[] used,
15
                       StringBuilder path, List<String> results) {
16
    // A permutation uses all characters; record only at full length.
17
    if (path.length() == chars.length) {
18
        results.add(path.toString());         // full-length leaf → record
19
        return;
20
    }
21
    for (int i = 0; i < chars.length; i++) {
22
        if (used[i]) continue;                 // already placed
23
        // Skip an equal sibling whose identical predecessor is still unused — collapses
24
        // duplicate permutations.
25
        if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) continue;  // dedup
26
        // Mark the character placed so deeper levels skip it.
27
        used[i] = true;                        // choose
28
        path.append(chars[i]);
29
        backtrack(chars, used, path, results); // explore
30
        // Pop the character; the next line unmarks it — both must be undone.
31
        path.deleteCharAt(path.length() - 1);  // un-choose: restore BOTH
32
        used[i] = false;
33
    }
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(n · n!) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s = "a" — One character → one permutation. Records ["a"] at the single full-length leaf.Explore edge cases

Edge cases handled

s = "a"One character → one permutation. Records ["a"] at the single full-length leaf.
s = "aa"The dedup skip blocks the second branch → only ["aa"], not ["aa", "aa"].
s = "ba"Sorted to a, b first, so output is ["ab", "ba"] in lexicographic order despite the input order.

Pitfalls

Sorting the result instead of the input — works but wastes an O(n·n!·log n!) sort.
Dropping the `!used[i-1]` condition in the dedup — over-skips and loses valid permutations.
Forgetting `used[i] = false` on backtrack — leaves characters marked and loses permutations.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; public List<String> permutations(String s) { char[] chars = s.toCharArray(); Arrays.sort(chars); // sort → lexicographic emissionExplore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing duplicate skip

With repeated characters, two identical letters generate the same permutation twice. The same-level skip collapses them so each distinct permutation appears once.

Explore the code comparison

Don't write this

for i in range(n):
    if used[i]:
        continue
    # no dedup → 'aa' produces ['aa', 'aa']
    used[i] = True; path.append(chars[i])

Write this instead

for i in range(n):
    if used[i]:
        continue
    if i > 0 and chars[i] == chars[i-1] and not used[i-1]:
        continue                       # dedup
    used[i] = True; path.append(chars[i])

Sorting the output, not the input

Sorting n! results at the end is far costlier than sorting the n characters once. Iterating sorted characters emits permutations already in order.

Explore the code comparison

Don't write this

List<String> all = generateAll(s);
Collections.sort(all);   // O(n · n! · log n!)
return all;

Write this instead

char[] chars = s.toCharArray();
Arrays.sort(chars);      // O(n log n), once
// backtrack emits in lexicographic order

Asymmetric backtrack

Choosing sets used[i] = true and appends; if un-choose only pops, the character stays marked for every sibling branch and most permutations vanish.

Explore the code comparison

Don't write this

used[i] = True; path.append(chars[i])
backtrack()
path.pop()                # used[i] never reset!

Write this instead

used[i] = True; path.append(chars[i])
backtrack()
path.pop(); used[i] = False   # restore BOTH

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sort + backtracking with used[] and same-level duplicate skip (lexicographic emission)

Code pattern to memorize

chars = sorted(s)

def backtrack(path):
    if len(path) == n: emit(''.join(path)); return
    for i in range(n):
        if used[i]: continue
        if i > 0 and chars[i] == chars[i-1] and not used[i-1]: continue  # dedup
        used[i] = True; path.append(chars[i])
        backtrack(path)
        path.pop(); used[i] = False

Rules to remember

1Sort the characters first — iterating them in order is what makes the output lexicographic without a post-sort.
2Use a used[] array (no start index) so every position can draw any not-yet-placed character — order matters in permutations.
3Dedup repeated letters with if chars[i] == chars[i-1] and not used[i-1]: continue — skips identical siblings at the same level so each distinct permutation appears once.
4Restore both path.pop() and used[i] = False on backtrack — asymmetric undo is the classic bug.
5Emit a copy/join at a full-length leaf only; partial paths aren't permutations.

Use this pattern when

All arrangements of a string/array, especially required in sorted order
Lexicographic enumeration where a stream of permutations is consumed in order
Input may contain repeated characters and duplicates must be collapsed
Anagram listing, password/keyspace enumeration of small length

Choose another pattern when

Only the NEXT permutation is needed → use next_permutation (O(n)), not full enumeration
Only the COUNT of distinct permutations → it's n! / (product of duplicate factorials), no enumeration
All characters distinct and order of output irrelevant → plain permutations, skip sort + dedup
n is large (> ~10) → n! is infeasible to enumerate

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Permutations II
Coming soon
Permutations of an array with duplicates — exactly this sort + same-level skip on integers.
Next Permutation
Coming soon
Only the single next ordering in O(n) — find the pivot, swap, reverse the suffix. No enumeration.
Subsets II
Coming soon
Same duplicate-skip idea applied to subsets instead of permutations.

Same pattern

←

Crossword Puzzle

Continue · Next problem

The Power Sum