<aside> 🐳 What is a Graph?

• Directed vs. Undirected, Cyclic vs. Acyclic
• Graph Terminologies:
• Helpful resource: https://leetcode.com/explore/learn/card/graph/
• review BFS and Topo between 08/17 - 08/23 </aside>

<aside> 📌 Depth-First Search Algorithm

• Backtracking describes the behavior of DFS - 从一个分支遍历完，回到母节点再去尝试其他分支。

• Keywords:

  • All possible solution. Whether the solution exsits…

• DFS题 Key Questions to Ask：

  • How many levels in the recursion tree? What does it store on each level?
  • How many different states should we try to put on each level? Base case(find all solutions)

• Typical Problems

  • subset母题：
    • Pattern: Taking some element(s) and remove some element(s) ⇒ 加或者不加
  • combination问题：all subsets,
  • permutation题：

• 模版：

  // dfs helper function
  private void findAllSolutions(input needed for each layer of search) {
  	// 1. base case - already found all solutions
  
  	// 2. check one element during each layer of search.
  	// 2.1 进入下一层去搜索之前，在当前层要做什么操作？ - 加,但是不能盲目的加。明知道分支不是解的话，别浪费时间和空间 => 剪枝
  	findAllSolutions(input, cur, res);
  	// 2.2 backtracking - 返回到当前层时需要做什么事情？ - 吐, 吃吐守
  	
  }
  

• 明知道有些分支不对的话，不要去搜索 ⇒ 剪枝。 要不然浪费时间和空间。 </aside>

<aside> 🐳 易错点：

StringBuilder APIs:

sb.append(element)
sb.deleteCharAt(index)
sb.toString()
sb.length()

</aside>

<aside> 🌵 Table of Contents

</aside>

Subset题

Date: August 15, 2023

Problem: Subsets (no dup) - 经典好题3种方法

Date: August 18, 2023

Problem: Subsets of Size K (no dup)

Date: August 18, 2023

Problem: Subsets II (has dup)

Date: August 18, 2023

Problem: All Subsets of Size K (has dup)

Date: August 18, 2023