General All Permutations
Given a string of unique letters, find all of its distinct permutations.
Permutation means arranging things with an order. For example, permutations of [1, 2] are [1, 2] and [2, 1]. Permutations are best visualized with trees.
The number of permutations is given by n! (we looked at factorial in Recursion Review). The way to think about permutation is to imagine you have a bag of 3 letters. Initially, you have 3 letters to choose from, you pick one out of the bag. Now you are left with 2 letters, you pick again now there's only 1 letter. The total number of choices is 3*2*1 = 6 (hence we have 6 leaf nodes in the above tree).
Input
letters: a string of unique letters
Output
all of its distinct permutations
Examples
Example 1:
Input:
letters = abc
Output: abc acb bac bca cab cba
Explanation:
All permutations.
Try it yourself
Solution
Permutation is very similar to combination except the same element can NOT be used more than once.
For example, if we had picked a for our first letter, we can not use it again for other letters for the same permutation.
Here's the state-space tree:
Additional states
This is where we need an additional state to keep track of the letters we have already used.
We will introduct a used list to record which letters are already used. used[i] == true means ith letter in the origin list has been used.
This variable is passed to the recursive calls to skip the used letters when we branch out.
Revert additional states
Note that in the Generate All Parentheses problem, the additional states openCount and closeCount are copied and in the recursive calls.
The used variable, however, is passed by reference in a recursive call.
Therefore we have to "undo" the update much like how we undo the update in path variable by popping the last element after the recursive call.
Applying our template
function dfs(start_index, path, [...additional states]): if is_leaf(start_index): report(path) return for child in get_edges(start_index, [...additional states]): # prune if needed if not is_valid(child): continue path.add(child) update(start_index) if additional states: update(...additional states) dfs(start_index, path, [...additional states]) # revert(...additional states) if necessary e.g. permutations path.pop()
Fill in the logics:
is_leaf:start_index == letters.lengthget_edges: each letter in the inputis_valid: if a letter is usedused[i] == True, then we skip it...additional states:usedto record which letter is used in the current pathrevert(...additional states): setused[i] = False
Here's the complete code implementation:
1def permutations(letters: str) -> list[str]:
2 res: list[str] = []
3 path: list[str] = []
4 used = [False] * len(letters)
5
6 def dfs(start_index: int) -> None:
7 if start_index == len(letters):
8 res.append("".join(path))
9 return
10
11 for i, letter in enumerate(letters):
12 # skip used letters
13 if used[i]:
14 continue
15 # add letter to permutation, mark letter as used
16 path.append(letter)
17 used[i] = True
18 dfs(start_index + 1)
19 # remove letter from permutation, mark letter as unused
20 path.pop()
21 used[i] = False
22
23 dfs(0)
24 return res
25
26if __name__ == "__main__":
27 letters = input()
28 res = permutations(letters)
29 for line in sorted(res):
30 print(line)
311import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8 private static void dfs(Integer startIndex, List<Character> path, boolean[] used, List<String> res, char[] letters) {
9 if (startIndex == used.length) {
10 // make a deep copy since otherwise we'd be append the same list over and over
11 res.add(path.stream()
12 .map(e -> e.toString())
13 .collect(Collectors.joining()));
14 return;
15 }
16 for (int i = 0; i < used.length; i++) {
17 // skip used letters
18 if (used[i])
19 continue;
20 // add letter to permutation, mark letter as used
21 path.add(letters[i]);
22 used[i] = true;
23 dfs(startIndex + 1, path, used, res, letters);
24 // remove letter from permutation, mark letter as unused
25 path.remove(path.size() - 1);
26 used[i] = false;
27 }
28 }
29
30 public static List<String> permutations(String s) {
31 char[] letters = s.toCharArray();
32 List<String> res = new ArrayList<>();
33 dfs(0, new ArrayList<>(), new boolean[letters.length], res, letters);
34 return res;
35 }
36
37 public static void main(String[] args) {
38 Scanner scanner = new Scanner(System.in);
39 String letters = scanner.nextLine();
40 scanner.close();
41 List<String> res = permutations(letters);
42 res.stream().sorted().forEach(System.out::println);
43 }
44}
451using System;
2using System.Collections.Generic;
3
4class Solution
5{
6 private static void Dfs(int startIndex, List<char> path, bool[] used, List<string> res, string letters)
7 {
8 if (startIndex == used.Length)
9 {
10 res.Add(string.Join("", path));
11 return;
12 }
13 for (int i = 0; i < used.Length; i++)
14 {
15 // skip used letters
16 if (used[i]) continue;
17 // add letter to permutation, mark letter as used
18 path.Add(letters[i]);
19 used[i] = true;
20 Dfs(startIndex + 1, path, used, res, letters);
21 // remove letter from permutation, mark letter as unused
22 path.RemoveAt(path.Count - 1);
23 used[i] = false;
24 }
25 }
26
27 public static List<string> Permutations(string letters)
28 {
29 List<string> res = new List<string>();
30 Dfs(0, new List<char>(), new bool[letters.Length], res, letters);
31 return res;
32 }
33
34 public static void Main()
35 {
36 string letters = Console.ReadLine();
37 List<string> res = Permutations(letters);
38 res.Sort();
39 foreach (string line in res)
40 {
41 Console.WriteLine(line);
42 }
43 }
44}
451"use strict";
2
3function permutations(letters) {
4 function dfs(startIndex, path, used, res) {
5 if (startIndex === letters.length) {
6 res.push(path.join(""));
7 return;
8 }
9 for (let i = 0; i < letters.length; i++) {
10 // skip used letters
11 if (used[i]) continue;
12 // add letter to permutation, mark letter as used
13 path.push(letters[i]);
14 used[i] = true;
15 dfs(startIndex + 1, path, used, res);
16 // remove letter from permutation, mark letter as unused
17 path.pop();
18 used[i] = false;
19 }
20 }
21 const res = [];
22 letters = [...letters];
23 dfs(0, [], new Array(letters.length).fill(false), res);
24 return res;
25}
26
27function* main() {
28 const letters = yield;
29 const res = permutations(letters);
30 res.sort();
31 for (const line of res) {
32 console.log(line);
33 }
34}
35
36class EOFError extends Error {}
37{
38 const gen = main();
39 const next = (line) => gen.next(line).done && process.exit();
40 let buf = "";
41 next();
42 process.stdin.setEncoding("utf8");
43 process.stdin.on("data", (data) => {
44 const lines = (buf + data).split("\n");
45 buf = lines.pop();
46 lines.forEach(next);
47 });
48 process.stdin.on("end", () => {
49 buf && next(buf);
50 gen.throw(new EOFError());
51 });
52}
531function permutations(letters: string): string[] {
2 function dfs(startIndex: number, path: string[], used: boolean[], res: string[]): void {
3 if (startIndex === letters.length) {
4 res.push(path.join(""));
5 return;
6 }
7 for (let i = 0; i < letters.length; i++) {
8 // skip used letters
9 if (used[i]) continue;
10 // add letter to permutation, mark letter as used
11 path.push(letters[i]);
12 used[i] = true;
13 dfs(startIndex + 1, path, used, res);
14 // remove letter from permutation, mark letter as unused
15 path.pop();
16 used[i] = false;
17 }
18 }
19 const res: string[] = [];
20 const used: boolean[] = new Array(letters.length).fill(false);
21 dfs(0, [], used, res);
22 return res;
23}
24
25function* main() {
26 const letters = yield;
27 const res = permutations(letters);
28 res.sort();
29 for (const line of res) {
30 console.log(line);
31 }
32}
33
34class EOFError extends Error {}
35{
36 const gen = main();
37 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
38 let buf = "";
39 next();
40 process.stdin.setEncoding("utf8");
41 process.stdin.on("data", (data) => {
42 const lines = (buf + data).split("\n");
43 buf = lines.pop() ?? "";
44 lines.forEach(next);
45 });
46 process.stdin.on("end", () => {
47 buf && next(buf);
48 gen.throw(new EOFError());
49 });
50}
511#include <algorithm>
2#include <iostream>
3#include <string>
4#include <vector>
5
6void dfs(int startIndex, std::vector<char>& path, std::vector<bool>& used, std::vector<std::string>& res, std::string& letters) {
7 if (startIndex == letters.size()) {
8 // make a deep copy, otherwise we'd be appending the same list over and over
9 std::string s(path.begin(), path.end());
10 res.emplace_back(s);
11 return;
12 }
13 for (int i = 0; i < letters.size(); i++) {
14 // skip used letters
15 if (used[i]) continue;
16 // add letter to permutation, mark letter as used
17 path.emplace_back(letters[i]);
18 used[i] = true;
19 dfs(startIndex + 1, path, used, res, letters);
20 // remove letter from permutation, mark letter as unused
21 path.pop_back();
22 used[i] = false;
23 }
24}
25
26std::vector<std::string> permutations(std::string letters) {
27 std::vector<std::string> res;
28 std::vector<char> path;
29 std::vector<bool> used(letters.size(), false);
30 dfs(0, path, used, res, letters);
31 return res;
32}
33
34int main() {
35 std::string letters;
36 std::getline(std::cin, letters);
37 std::vector<std::string> res = permutations(letters);
38 std::sort(res.begin(), res.end());
39 for (const std::string& line : res) {
40 std::cout << line << '\n';
41 }
42}
431package main
2
3import (
4 "bufio"
5 "fmt"
6 "os"
7 "sort"
8)
9
10func permutations(letters string) []string {
11 var res []string
12
13 var dfs func(int, []byte, []bool)
14 dfs = func(startIndex int, path []byte, used []bool) {
15 if startIndex == len(letters) {
16 res = append(res, string(path))
17 return
18 }
19 for i, letter := range letters {
20 // skip used letters
21 if used[i] {
22 continue
23 }
24 // add letter to permutation, mark letter as used
25 path = append(path, byte(letter))
26 used[i] = true
27 dfs(startIndex+1, path, used)
28 // remove letter from permutation, mark letter as unused
29 path = path[:len(path)-1]
30 used[i] = false
31 }
32 }
33
34 dfs(0, []byte{}, make([]bool, len(letters)))
35 return res
36}
37
38func main() {
39 scanner := bufio.NewScanner(os.Stdin)
40 scanner.Scan()
41 letters := scanner.Text()
42 res := permutations(letters)
43 sort.Strings(res)
44 for _, row := range res {
45 fmt.Println(row)
46 }
47}
48Time Complexity
We have n letters to choose in the first level, n - 1 choices in the second level and so on therefore the number of strings we generate is n * (n - 1) * (n - 2) * ... * 1, or O(n!) (see math basics if you need a refresher on factorial).
Since each string has length n, generating all the strings requires O(n * n!) time.
Space Complexity
The total space complexity is given by the amount of space required by the strings we're constructing. Like
the time complexity, the space complexity is also O(n * n!).