前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在 离开某个节点之后的那个时间点执行。

• path
• selection list
• end condition

1
2
3
4
5
6
7
8
9

result = []
def backtrack(path, selection_list):
  if match:
    result.add(path)
    return
  for selection in selection_list:
    do_select()
    backtrack(path, selection_list)
    backtrack_select()

Problems

permutation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

var res = new LinkedList<>();

List<List<Integer>> permute(int[] nums) {
  var track = new LinkedList<>();
  backtrack(nums, track);
  return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
  if (track.size() == nums.length) {
    res.add(new LinkedList<>(track));
    return;
  }
  for (int i = 0; i < nums.length; i++) {
    if (track.contains(nums[i])) {
      continue;
    }
    track.add(nums[i]);
    backtrack(nums, track);
    track.removeLast();
  }
}

LeetCode Problems

• letter combinations of a phone number
• generate parentheses
• sudoku solver
• combination sum
• combination sum II
• permutations
• permutations II
• n-queens
• n-queens II
• permutation sequence
• combinations
• subsets
• word search
• gray code
• subsets II
• restore IP addresses
• word ladder II
• palindrome partitioning
• design add and search words data structure
• word search II
• combination sum III
• additive number
• count numbers with unique digits
• binary watch
• beautiful arrangement
• letter case permutation
• split array into fibonacci sequence
• unique paths III
• number of squareful arrays
• letter tile possibilities
• maximum length of a concatenated string with unique characters
• count sorted vowel strings
• distribute repeating integers
• maximize grid happiness
• mimimum incompatibility
• count of matches in tournament