# LeetCode Distilled Series: 46. Finding all Permutations

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

Input:

`['a', 'b', 'c']`

Output:

`[['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]`

# Intuition

This is a 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).

# 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 list to represent permutation constructed so far, `path`
2. A list to record which letters are already used, `used`, `used[i] == true` means `i`th letter in the origin list has been used.
`def permutations(l):               def dfs(path, used, res):        if len(path) == len(l):            res.append(path[:]) # note [:] make a deep copy since otherwise we'd be append the same list over and over            return                for i, letter in enumerate(l):            # skip used letters            if used[i]:                continue            # add letter to permutation, mark letter as used            path.append(letter)            used[i] = True            dfs(path, used, res)            # remove letter from permutation, mark letter as unused            path.pop()            used[i] = False                res = []    dfs([], [False] * len(l), res)    return res`

In the exit logic of the above solution, we append a deep copy of 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:

`>>> res = []>>> path = []>>> for i in range(3):...     path.append(i)...     res.append(path)...>>> res[[0, 1, 2], [0, 1, 2], [0, 1, 2]]`

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.

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator