Permutations Prereq: Backtracking
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 ']]
Try it yourself
Explanation 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).
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.
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:
A list to represent permutation constructed so far, path
A list to record which letters are already used, used
, used[i] == true
means i
th letter in the origin list has been used. Python Java JavaScript 1 1 def permutations ( l ):
2 - # WRITE YOUR BRILLIANT CODE HERE
2 + def dfs ( path, used, res ):
3 + if len(path) == len(l):
4 + res.append(path[:]) # note [:] make a deep copy since otherwise we'd be append the same list over and over
5 + return
6 +
7 + for i, letter in enumerate(l):
8 + # skip used letters
9 + if used[i]:
10 + continue
11 + # add letter to permutation, mark letter as used
12 + path.append(letter)
13 + used[i] = True
14 + dfs(path, used, res)
15 + # remove letter from permutation, mark letter as unused
16 + path.pop()
17 + used[i] = False
18 +
19 + res = []
20 + dfs([], [ False ] * len(l), res)
21 + return res
22 +
3 23 if __name__ == "__main__" :
4 24 res = permutations(list(input()))
5 25 print( ' ' .join(sorted( '' .join(x) for x in res)))
Expand 6 lines ... 7 7 class Solution {
8 8
9 9 public static List<List<Character>> permute( char [] letters) {
10 - // WRITE YOUR BRILLIANT CODE HERE
10 + List<List<Character>> res = new ArrayList<>();
11 + dfs( new ArrayList<>(), new boolean [letters.length], res, letters);
12 + return res;
11 13 }
12 14
15 + private static void dfs (List<Character> path, boolean [] used, List<List<Character>> res, char [] letters) {
16 + if (path.size() == used.length) {
17 + // make a deep copy since otherwise we'd be append the same list over and over
18 + res.add( new ArrayList<Character>(path));
19 + return ;
20 + }
21 +
22 + for ( int i = 0 ; i < used.length; i++) {
23 + // skip used letters
24 + if (used[i]) continue ;
25 + // add letter to permutation, mark letter as used
26 + path.add(letters[i]);
27 + used[i] = true ;
28 + dfs(path, used, res, letters);
29 + // remove letter from permutation, mark letter as unused
30 + path.remove(path.size() - 1 );
31 + used[i] = false ;
32 + }
33 + }
34 +
13 35 public static void main (String[] args) throws IOException {
14 36 Scanner scanner = new Scanner(System.in);
15 37 char [] input = scanner.nextLine().toCharArray();
16 38 scanner.close();
Expand 9 lines ...
1 1 const readline = require ( 'readline' );
2 2
3 3 function permutations ( letters ) {
4 - // WRITE YOUR BRILLIANT CODE HERE
4 + let res = [];
5 + dfs(letters, [], Array (letters.length).fill( false ), res);
6 + return res;
5 7 }
6 8
9 + function dfs ( letters, path, used, res ) {
10 + if (path.length == letters.length) {
11 + // make a deep copy since otherwise we'd be append the same list over and over
12 + res.push( Array .from(path));
13 + return ;
14 + }
15 + for ( let i = 0 ; i < letters.length; i++) {
16 + // skip used letters
17 + if (used[i]) continue ;
18 + // add letter to permutation, mark letter as used
19 + path.push(letters[i]);
20 + used[i] = true ;
21 + dfs(letters, path, used, res);
22 + // remove letter from permutation, mark letter as unused
23 + path.pop();
24 + used[i] = false ;
25 + }
26 + }
27 +
7 28 const rl = readline.createInterface(process.stdin);
8 29 rl.on( 'line' , ( input ) => {
9 30 const arr = input.split( '' );
10 31 rl.close();
Expand 3 lines ...
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 we have a new constraint "number of letters left" while deciding which subtree goes down to.
Note on deep copy 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.
Loading full content...