 # 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:

``1letters = abc``

Output: `abc acb bac bca cab cba `

Explanation:

All permutations.

## 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: 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 `i`th 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.

Note that in the Generate All Parentheses problem, the additional states `openCount` and `closeCount` are copied and in the recurive 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

``````1function dfs(start_index, path, [...additional states]):
2  if is_leaf(start_index):
3    report(path)
4    return
5  for child in get_edges(start_index, [...additional states]):
6    # prune if needed
7    if not is_valid(child):
8      continue
10    update(start_index)
14    # revert(...additional states) if necessary e.g. permutations
15    path.pop()``````

Fill in the logics:

• `is_leaf`: `start_index == letter.length`
• `get_edges`: each letter in the input
• `is_valid`: if a letter is used `used[i] == True`, then we skip it
• `...additional states`: `used` to record which letter is used in the current path
• `revert(...additional states)`: set `used[i] = False`

Here's the complete code implementation:

``````1from typing import List
2
3def permutations(letters):
4    def dfs(start_index, path, used, res):
5        if start_index == len(letters):
6            res.append(''.join(path))
7            return
8
9        for i, letter in enumerate(letters):
10            # skip used letters
11            if used[i]:
12                continue
13            # add letter to permutation, mark letter as used
14            path.append(letter)
15            used[i] = True
16            dfs(start_index + 1, path, used, res)
17            # remove letter from permutation, mark letter as unused
18            path.pop()
19            used[i] = False
20
21    res = []
22    dfs(0, [], [False] * len(letters), res)
23    return res
24
25if __name__ == '__main__':
26    letters = input()
27    res = permutations(letters)
28    for line in sorted(res):
29        print(line)
30``````
``````1import 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
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
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        Collections.sort(res);
43        for (String line : res) {
44            System.out.println(line);
45        }
46    }
47}
48``````
``````1using 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        {
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
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    {
37        List<string> res = Permutations(letters);
38        res.Sort();
39        foreach (string line in res)
40        {
41            Console.WriteLine(line);
42        }
43    }
44}
45``````
``````1function permutations(letters) {
2    function dfs(startIndex, path, used, res) {
3        if (startIndex == letters.length) {
4            return res.push(path.join(''));
5        }
6        for (let i = 0; i < letters.length; i++) {
7            // skip used letters
8            if (used[i]) continue;
9            // add letter to permutation, mark letter as used
10            path.push(letters[i]);
11            used[i] = true;
12            dfs(startIndex + 1, path, used, res);
13            // remove letter from permutation, mark letter as unused
14            path.pop();
15            used[i] = false;
16        }
17    }
18    const res = [];
19    letters = [...letters];
20    dfs(0, [], new Array(letters.length).fill(false), res);
21    return res;
22}
23
24function* main() {
25    const letters = yield;
26    const res = permutations(letters);
27    res.sort();
28    for (const line of res) {
29        console.log(line);
30    }
31}
32
33class EOFError extends Error {}
34{
35    const gen = main();
36    const next = (line) => gen.next(line).done && process.exit();
37    let buf = '';
38    next();
39    process.stdin.setEncoding('utf8');
40    process.stdin.on('data', (data) => {
41        const lines = (buf + data).split('\n');
42        buf = lines.pop();
43        lines.forEach(next);
44    });
45    process.stdin.on('end', () => {
46        buf && next(buf);
47        gen.throw(new EOFError());
48    });
49}
50``````
``````1#include <algorithm> // sort
2#include <iostream> // cin, cout
3#include <string> // getline, string
4#include <vector> // vector
5
6void dfs(int startIndex, std::vector<char> path, 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    bool used[letters.size()] = { false };
29    dfs(0, {}, used, res, letters);
30    return res;
31}
32
33int main() {
34    std::string letters;
35    std::getline(std::cin, letters);
36    std::vector<std::string> res = permutations(letters);
37    std::sort(res.begin(), res.end());
38    for (const std::string& line : res) {
39        std::cout << line << '\n';
40    }
41}
42``````

### Time 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 operation is `n * (n - 1) * (n - 2) * ... * 1`, or `O(n!)` (see math basics if you need a refresher on factorial).

### Space Complexity

The total space complexity is given by the height of the state-space tree, which is `O(n)` as we use all `n` elements.

Still not clear? Submit the part you don't understand to our editors.