ZXAlgorithm - C5 DFS

Outline
Recursion
Combination
Permutation
Graph
Non-recursion

0 Template

• All for finding all the outcomes must be DFS90% DFS is permutation or combination
• Three points of recursion: In my view is SDE
  Definition
  Divide
  Exit

1 Combination: related to time complexity(2^n)

Subsets
https://leetcode.com/problems/subsets/
https://leetcode.com/problems/subsets-ii/
http://www.lintcode.com/problem/subsets/
此类问题通用解法：
https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
https://www.jiuzhang.com/solution/subsets/#tag-highlight-lang-python
DC Definition: sorted, start, sublist, result Return: void
S: List<List<Integer>> results, List<Integer> subset, int[] nums, startIndex
D: subset.add(nums[i]), dfs, subset.remove(subset.size() - 1)
E: results.add(new ArrayList<Integer>(subset))
Subsets II
https://leetcode.com/problems/subsets-ii/
https://www.jiuzhang.com/solution/subsets-ii/#tag-highlight-lang-python
if i > index and nums[i] == nums[i-1]:
记得一定要大于index，否则子集里面重复的元素都没了
Combination sum
https://leetcode.com/problems/combination-sum/
https://www.jiuzhang.com/solution/combination-sum/#tag-highlight-lang-python
DC Definition: sorted, start, sublist, target, result Return: void
S: result, nums, combination, target, startindex
D: I != index && nums[i] == nums[I - 1] -> continue; target < 0 -> break;
comb.add(), dfs, removeE: target = 0 -> result.add(), return
Combination sum II
http://www.lintcode.com/problem/combination-sum-ii/ http://www.jiuzhang.com/solutions/combination-sum-ii/
同上多一个target
Palindrome Partitioning
https://leetcode.com/problems/palindrome-partitioning/
http://www.lintcode.com/problem/palindrome-partitioning/ http://www.jiuzhang.com/solutions/palindrome-partitioning/
https://www.jiuzhang.com/solutions/palindrome-partitioning/#tag-other-lang-python
其实也可以用上面的模板去写
S: String s; startIndex; results; subset;
D: subString = s.substring(startIndex, I + 1); !isPalindrome(subString) -> continue;
E: startIndex == s.length() -> add and return;

4 Permutation: related to time complexity(n!)

Permutations

Permutations
https://leetcode.com/problems/permutations/
http://www.lintcode.com/problem/permutations/ http://www.jiuzhang.com/solutions/permutations/
DC Definition: unsorted, sublist, result
S: results; sub; nums;
D: sub.contains(nums[i]) -> continue
E: sub.size() = nums.length -> results.add(), return
Permutations II
https://leetcode.com/problems/permutations-ii/
http://www.lintcode.com/problem/permutations-ii/ http://www.jiuzhang.com/solutions/permutations-ii/
S: results; sub; nums; visited;
D: visited[i] == 1 || (I != 0 && nums[i] == nums[I -1] && visited[I - 1] == 0) -> continue; the front is still in the front at the result;
E: sub.size() == nums.length() -> results.add(), return
N queens
Change this problem to permutation [] Integer
S: results; cols; n;
D: drawChessBoard(); isValid(cols, colnumn)E: col.size() == n -> results.add(), return

5 Search in a graph

• BFS: Word Ladder
  D: use bfs to find the shortest path

• Word Ladder2
  D: use bfs to find the shortest path, 并标注每一个点与起点的最短路径, then use dfs to find all possible paths in reverse direction，保证每一步都路径只加一

  
  

6 Recite

Tree Traversal
Preorder, Inorder, Post order,binary search tree iterator
Search tree iterator is same as inorder traversal

• Subsets/Combination
  S: results; sub; nums;
  D: sub.contains(nums[i]) -> continue
  E: sub.size() = nums.length -> results.add(), return
• Permutation
  DC Definition: sorted, start, sublist, result Return: void
  S: List<List<Integer>> results, List<Integer> subset, int[] nums, startIndex
  D: subset.add(nums[i]), dfs, subset.remove(subset.size() - 1)
  E: results.add(new ArrayList<Integer>(subset))
• Permutations 2
  S: results; sub; nums; visited;
  D: visited[i] == 1 || (I != 0 && nums[i] == nums[I -1] && visited[I - 1] == 0) -> continue; the front is still in the front at the result;
  E: sub.size() == nums.length() -> results.add(), return

7 Memory

S

for() {subset.add() dfs() subset.remove(subset.size() - 1) }
Use stack for tree traversal

D

Permutation and subsets and combination
Preorder and inorder non-recursive