Permutations

Given a string of unique letters, find all of its distinct permutations.

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

1`
2
3**Explanation**:
4

All permutations.

Try it yourself

Solution

Intuition

Classic combinatorial search problem. Let's apply the 3-step system from backtracking template.

1. Identify States

What state do we need to know whether we have reached a solution (and using it to construct a solution if the problem asks for it)?

  1. We need a state to keep track of the list of letters we have chosen for the current permutation

What state do we need to decide which child nodes should be visited next and which ones should be pruned?

  1. We have to know what are the letters left that we can still use (since each letter can only be used once)?

2. Draw the State-space Tree

3. DFS on the State-space tree

Using the backtracking template as basis, we add the two states we identified in step 1:

  1. A path list to represent permutation constructed so far.
  2. A used list to record which letters are already used. used[i] == true means ith letter in the origin list has been used.

Time Complexity: O(n!)

This is because we have n letters to choose from then n - 1 and so on therefore n * (n - 1) * (n - 2) * ... * 1

1from typing import List
2
3def permutations(letters):
4    def dfs(path, used, res):
5        if len(path) == 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(path, used, res)
17            # remove letter from permutation, mark letter as unused
18            path.pop()
19            used[i] = False
20
21    res = []
22    dfs([], [False] * len(letters), res)
23    return res
24
25if __name__ == '__main__':
26    letters = input()
27    res = permutations(letters)
28    for line in res:
29        print(line)
30

Feel free to revisit the DFS on tree animation to gain more intuition on how the code works with call stack.

Notice how similar the solution is to Ternary Tree Paths. The difference is that we have a new constraint "number of letters left" while deciding which subtree to go down to.

Note on deep copy

In the exit logic of the above solution, we append a deep copy of the path res.append(path[:]). This creates a new list with elements being the same as current elements of path. Consider what happens if we don't make the deep copy:

1>>> res = []
2>>> path = []
3>>> for i in range(3):
4...     path.append(i)
5...     res.append(path)
6...
7>>> res
8[[0, 1, 2], [0, 1, 2], [0, 1, 2]]
9

We get the same copy three times! Because append(path) actually appends a reference (memory address), we actually appended the same list three times. path.append(i) mutates the list and affects all references to that list. To fix this, we create a new list before we append.