Problem

Given a string s that contains no duplicate characters, generate all permutations of s. Return or print each permutation. For a string of length n there are n! permutations.

Examples

Example 1

1
2

Input: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"]
Similar Problems

Solution

Below are common approaches to generate all permutations when input values are distinct.

Method 1 — Prefix recursion (build-up)

Intuition

Fix a prefix prefix and recursively generate permutations of the remaining characters rest. Appending each character from rest to prefix produces permutations that start with that character.

Approach

  1. If rest is empty, prefix is a complete permutation — output it.
  2. Otherwise, for each index i in rest:
    • Choose rest[i], append it to prefix and recurse on rest without rest[i].
  3. This explores all n! permutations.

Edge cases:

  • Empty string -> single permutation "".
  • Very large n will produce huge output (n!) and is impractical to store; stream/print as generated.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
 public:
  // public entry point
  std::vector<std::string> permute(const std::string &s) {
    return permutePrefix("", s);
  }

 private:
  std::vector<std::string> permutePrefix(const std::string &prefix, const std::string &rest) {
    if (rest.empty()) return {prefix};
    std::vector<std::string> res;
    for (size_t i = 0; i < rest.size(); ++i) {
      std::string next_prefix = prefix + rest[i];
      std::string next_rest = rest.substr(0, i) + rest.substr(i + 1);
      auto sub = permutePrefix(next_prefix, next_rest);
      res.insert(res.end(), sub.begin(), sub.end());
    }
    return res;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

package main

func permutePrefix(prefix, rest string) []string {
  if len(rest) == 0 {
    return []string{prefix}
  }
  var res []string
  for i := 0; i < len(rest); i++ {
    nextPrefix := prefix + string(rest[i])
    nextRest := rest[:i] + rest[i+1:]
    sub := permutePrefix(nextPrefix, nextRest)
    res = append(res, sub...)
  }
  return res
}

// single-argument entry point
func Permute(s string) []string {
  return permutePrefix("", s)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  public List<String> permute(String s) {
    return permutePrefix("", s);
  }

  private List<String> permutePrefix(String prefix, String rest) {
    if (rest.length() == 0) return Collections.singletonList(prefix);
    List<String> res = new ArrayList<>();
    for (int i = 0; i < rest.length(); ++i) {
      String nextPrefix = prefix + rest.charAt(i);
      String nextRest = rest.substring(0, i) + rest.substring(i + 1);
      res.addAll(permutePrefix(nextPrefix, nextRest));
    }
    return res;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def permute_prefix(self, prefix: str, rest: str) -> list[str]:
    if not rest:
      return [prefix]
    res: list[str] = []
    for i in range(len(rest)):
      next_prefix = prefix + rest[i]
      next_rest = rest[:i] + rest[i+1:]
      res.extend(self.permute_prefix(next_prefix, next_rest))
    return res

  def permute(self, s: str) -> list[str]:
    return self.permute_prefix("", s)

Complexity

  • ⏰ Time complexity: O(n * n!) — generating n! permutations and constructing each permutation of length n.
  • 🧺 Space complexity: O(n) extra space for recursion stack (plus output size O(n * n!) if all permutations are stored).

Method 2 — In-place backtracking (swap)

Intuition

Fix a position index and swap each character from index..n-1 into that position, then recurse for index + 1. After recursion, swap back to restore the array (backtracking).

Approach

  1. Convert string to a mutable array a.
  2. Define backtrack(a, index):
    • If index == len(a): print a as a permutation.
    • For i from index to len(a)-1: swap a[index] and a[i], recurse backtrack(a, index+1), swap back.

Edge cases:

  • Works in-place and avoids allocating new strings every recursion level, reducing temporary allocations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
 public:
  std::vector<std::string> permute(std::string a) {
    return backtrack(a, 0);
  }

 private:
  std::vector<std::string> backtrack(std::string &a, int index) {
    if (index == (int)a.size()) return {a};
    std::vector<std::string> res;
    for (int i = index; i < (int)a.size(); ++i) {
      std::swap(a[index], a[i]);
      auto sub = backtrack(a, index + 1);
      res.insert(res.end(), sub.begin(), sub.end());
      std::swap(a[index], a[i]);
    }
    return res;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

package main

func backtrack(a []rune, index int) []string {
  if index == len(a) {
    return []string{string(a)}
  }
  var res []string
  for i := index; i < len(a); i++ {
    a[index], a[i] = a[i], a[index]
    sub := backtrack(a, index+1)
    res = append(res, sub...)
    a[index], a[i] = a[i], a[index]
  }
  return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  public List<String> permute(String s) {
    return backtrack(s.toCharArray(), 0);
  }

  private List<String> backtrack(char[] a, int index) {
    if (index == a.length) return Collections.singletonList(new String(a));
    List<String> res = new ArrayList<>();
    for (int i = index; i < a.length; ++i) {
      char tmp = a[index]; a[index] = a[i]; a[i] = tmp;
      res.addAll(backtrack(a, index + 1));
      tmp = a[index]; a[index] = a[i]; a[i] = tmp;
    }
    return res;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  def permute(self, s: str) -> list[str]:
    return self.backtrack(list(s), 0)

  def backtrack(self, a: list[str], index: int) -> list[str]:
    if index == len(a):
      return [''.join(a)]
    res: list[str] = []
    for i in range(index, len(a)):
      a[index], a[i] = a[i], a[index]
      res.extend(self.backtrack(a, index + 1))
      a[index], a[i] = a[i], a[index]
    return res

Complexity

  • ⏰ Time complexity: O(n * n!).
  • 🧺 Space complexity: O(n) recursion depth; additional O(1) extra beyond input.

Method 3 — Iterative using lexicographic next_permutation

Intuition

If you produce permutations in lexicographic order (starting with a sorted string), the next_permutation operation transforms the current permutation into the next one in O(n) time per permutation.

Approach

  1. Sort the characters of s.
  2. Output the current permutation.
  3. Repeatedly apply next_permutation until no next permutation exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
 public:
  std::vector<std::string> permute(std::string s) {
    std::sort(s.begin(), s.end());
    std::vector<std::string> res;
    do {
      res.push_back(s);
    } while (std::next_permutation(s.begin(), s.end()));
    return res;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

package main

import "sort"

func nextPermutation(a []rune) bool {
  i := len(a) - 2
  for i >= 0 && a[i] >= a[i+1] {
    i--
  }
  if i < 0 {
    return false
  }
  j := len(a) - 1
  for a[j] <= a[i] {
    j--
  }
  a[i], a[j] = a[j], a[i]
  for l, r := i+1, len(a)-1; l < r; l, r = l+1, r-1 {
    a[l], a[r] = a[r], a[l]
  }
  return true
}

func iterative(s string) []string {
  a := []rune(s)
  sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
  var res []string
  for {
    res = append(res, string(a))
    if !nextPermutation(a) {
      break
    }
  }
  return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;

class Solution {
  public List<String> permute(String s) {
    char[] a = s.toCharArray();
    Arrays.sort(a);
    List<String> res = new ArrayList<>();
    do {
      res.add(new String(a));
    } while (nextPermutation(a));
    return res;
  }

  private boolean nextPermutation(char[] a) {
    int i = a.length - 2;
    while (i >= 0 && a[i] >= a[i+1]) i--;
    if (i < 0) return false;
    int j = a.length - 1;
    while (a[j] <= a[i]) j--;
    char tmp = a[i]; a[i] = a[j]; a[j] = tmp;
    for (int l = i+1, r = a.length-1; l < r; l++, r--) {
      tmp = a[l]; a[l] = a[r]; a[r] = tmp;
    }
    return true;
  }
}
1
2
3
4
5
6

import itertools

class Solution:
class Solution:
  def permute(self, s: str) -> list[str]:
    return [''.join(p) for p in itertools.permutations(s)]

Complexity

  • ⏰ Time complexity: O(n * n!) overall; next_permutation costs O(n) per permutation.
  • 🧺 Space complexity: O(n) extra space.