adaxjin

/*
@DFS
https://leetcode.com/problems/generate-parentheses/

check delta = #(() - #())

1. at the end delta == 0
2. in the middle, delta always >= 0
3. 只能描述单一括号的关系，不能描述不同种括号嵌套的关系
*/

adaxjin

/*
@DFS
https://leetcode.com/problems/remove-invalid-parentheses/

分叉：看到一个左括号或右括号，删掉还是保留
非括号只保留
只有一种括号，还是用delta

两个参数rmL rmR如何计算
- 中间过程中delta < 0，右括号多了，rmR++

adaxjin

/*
@DFS
https://leetcode.com/problems/word-search/

Clarify：
- 方向：4 or 2（4 Word Search）
- board的字可不可以复用（不行）
- 起点有没有要求（没有）

图上搜索，无向，与权值无关，无最短距离 → DFS

adaxjin

/*
@DFS
分叉：看到一个左括号或右括号，删掉还是保留
非括号只保留
只有一种括号，还是用delta

两个参数rmL rmR如何计算

- 中间过程中delta < 0，右括号多了，rmR++
- 结束时delta != 0，左括号多，rmL++

adaxjin

/*
@DFS
https://leetcode.com/problems/restore-ip-addresses/


拼数分叉：有固定模式
 - 分叉：每个数字后面都可以加什么：加点，拼数（下一位数字）
 - 最多加多少个（位数限制）：数字最长3位
 
Code结构

adaxjin

/*
@DFS
*/

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        dfs(nums, res, new ArrayList<>(), 0);
        return res;

adaxjin

/*
@Stack
@Parentheses

if left - store in stack
if right - stack not empty + match
*/

class Solution {
    public boolean isValid(String s) {

adaxjin

//@DFS

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(n, k, res, new ArrayList<>(), 1);
        return res;
    }
    
    private void dfs (int n, int k, List<List<Integer>> res, List<Integer> path, int idx){

adaxjin

/*
@DFS
因为可以取重复元素，搜索树长这样：
e.g. candidates = [2,3,6,7], target = 7

               2                  3           ...
      /     /     \    \
   2        3      4    7       ...
/ / \ \    /|\     /\   | 
2 3 6 7   3 6 7   6 7   7       ...

adaxjin

/*
@DFS

先sort，dfs时遇到重复跳过(注意查不出界)
这道题不允许拿重复元素，区别是dfs时idx是i+1不是i，即下一层从下一个元素开始
*/

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();