DFS Problems

DFS

BFS & DFS 区别

BFS一般是最近距离，最少步数的问题
DFS一般是最远距离，最多步，最深

Split String

Letter Combinations of a Phone Number

因为given number的形式是String，那么String数字（‘0’，‘1’…）有什么特殊的操作方法？在不转换type的情况下输入我们String里面的那个数字（0，1，..）
ind digit = strDigits.charAt(i) - '0'

比如strDigits = "813" 当 i = 2, 要取的char(数字)是‘3’ 那么'8' - '0' = 8 ACSII Table

'0' -> 48
'1' -> 49
...
'9' -> 57
___________________________
'0' - '0' -> 48 - 48 = 0
'1' - '0' -> 49 - 48 = 1
...
'9' - '0' -> 57 - 48 = 9

将电话键盘上那种数字-字母（类似9键键盘）的mapping放在代码里：

String[] phone = {
               "", //0位置空出来
               "", "abc", "def",  //1键里面没有代表的数字
               "ghi", "jkl", "mno", 
               "pqrs", "tuv", "wxyz"};

Combination Sum II

题目信息：

从Collection 中抽取，有重复的元素
不可重复使用单个元素
unique组合
不可重复使用单个元素的时候，在for loop中的dfs中，param index = i+1,因为下一次递归（也就是下一位填补的元素）的for loop要从自己的下一个开始，不可以重复算自己。
因为给的数组里有重复的数字，但是你的结果必须是unique组合，所以for loop里面要控制，当前数字和前一个相同时，continue loop。

Combination Sum

题目信息：

从Set中抽取
可重复使用某个数
unique组合（只有组合，没有排列的意思？）
应该确认是否有负数

思路：
先sort，当这一个加进来已经太大，后面更大的都不用加了（在dfs时有一个if(remainSum < 0) return跳出递归
递归函数的param有：int[] 原数组, index, target,子集comb,总机result
递归退出条件是target == 0
将comb添加到res时需要deep copy res.add(new ArrayList<Integer>(comb))
递归内用一个for loop循环，从该index到数组末尾，好比做组合时，我们从2、3、6、7数一遍带2的满足条件的组合，然后3、6、7，但我们不会往回走，因为所有带2的已经再index=2的for loop中考虑过了
backtracking，最后要在temp_sublist中移除该集合中最后一个，也就是回到上一步combination.remove(combination.size() - 1)

N-Queens

Subsets

given a set of distinct intergers
subset: no duplicates!

思路：
子集的概念：2^N 个，包括自己和空集
dfs的params包括原集合int[] nums,起始序号int index,子集List<Integer> path,子集的总集List<List<Integer>> res
建好sublist和res两个list后，在call dfs之前应该先res.add(sublist)保证子集为空集的情况
dfs里面就是for loop，每一次sublist增加新成员，即新的子集出现，res就添加一次sublist
for loop里面call dfs时，传入i + 1
backtracking 依然有

Subsets II

组合
given有重复的元素

和permutation很像！

Permutations

given a collection of distinct integers

排列的基本思考：
比如：给出三个数，列出这三个数所有的排列方式
所有子集comb的长度都等于3，不可以多、不可以少
每一次换一个数字开头的时候，for loop的遍历是整个数组（除去当前数字自己），所以for loop起点永远是0，而不是index。所以dfs的param里面没有index！
boolean[] visited是用来辨别当前数字的，在for loop中用来跳过自己（补上第二位后，将第二位数boolean = true; 然后跳进第三位数的dfs，第三位数dfs的for loop中应该跳过前两个位置上的数字…以此类推）
注意这样的visited array标记的是哪个index已经被访问
for loop最后依然是backtracking： path.remove(path.size() - 1)，但是注意还要改变boolean，移除后就把boolean设置回false，visited[i] = false

Permutations II

区别：given collection 会有重复的数字（不是distinct）
没有说全是正数，所以会有0和负数(？)
一定要先Sort，否则后面的检验nums[i-1] == nums[i]没有意义，comb该重复还是会重复
given collection有重复数字时，如下考虑if。比如说[1,1,1,2]当第一个1全部考虑过以后，回到第一层for loop，开始i = 2，此时又是1打头，又会把整个数组别的元素在1后面排列一遍，此时会得到和上一个loop完全一样的结果集（排列结果）
```
  for-loop {
  if (visited[i] || i > 0 && nums[i] == nums[i-1] && !visited[i-1])
      continue;
}
```
Word Pattern II

Word Ladder II

Path Sum III

任意节点到任意节点的path，val之和等于sum
有负数

思路：
每一个节点作为起点，都要一直遍历到尾（null）比如说sum=8, root=10, root.right=-2, root.right.right=0, 那就有两条，前一条==8后还要保持这个path往下走，万一后面有0呢！
双重递归
第一重递归（内递归）是从root一直遍历到叶节点，收获所有path的数量count
第二重递归（外递归）是改变root，每一个节点都做一次root

Increasing Sequences

确认increasing中“等于”的情况怎么判断，本题等于也算作increasing，也就是说[4,,7,7]也算符合条件的comb
题目说given array里面的数字范围[-100, 100]
在dfs中建一个byte[] visited = new byte[201]将nums[i]编码到visited里面
注意：此时visited标记的不是index，是内容， 也就是说哪个数字被访问过，那么nums[2]是7，nums[3]也是7，在同一个dfs的执行中，前者访问过就不会访问后者，不会有两个[4,7]
这个思想可以用在subsets II，原集合里有重复，但是最后返回要求unique comb。只不过subsets II里面没有限定integer的大小，不可以用一个固定长度的byte array去哈希，但是用set储存是一样的原理。
每次dfs时新建一个hashset，如果set不包含nums[i]，执行for loop，添加进去。注意最后不需要remove，因为进入新的dfs会有新的set。
在这个case中，用hashset会慢。
在increasing sequences例子中，用byte array快。所以感觉array时比collection快

Factor Combinations

返回n的约数集合，不包括1和自己。

在dfs的helper里面，return条件是```if (n == 1 && list.size() > 1)``
for loop将从2到n的所有数都当作约数试一次，一定要是for (int i = diviser; i <= n; i++)
如果除不尽跳过if..continue
依然要注意添加的时候是new ArrayList<>(list)
递归时参数，n变成n/diviser, 但diviser保持不变，一个约数走到底，再换

Solution space:

Permutations: N!

Combinations: C(k,N) = N! / ( (N-k)! k! )

Subsets: 2^N

since each element could be absent or present.

Redundant Connection

无向图DFS比较通用的模板

public int[] findRedundantConnection(int[][] edges) {
        int m = edges.length;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 1; i <= m; i++) {
            map.put(i, new HashSet<>());
        }
        
        for (int[] edge : edges) {
            if (dfs(new HashSet<>(), map, edge[0], edge[1])) return edge;
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }
        
        return new int[]{-1,-1};
    }
    
    private boolean dfs(Set<Integer> visited, Map<Integer, Set<Integer>> map,
                       int src, int target) {
        if (src == target) return true;
        visited.add(src);
        for (int next : map.get(src)) {
            if (!visited.contains(next)) {
                if (dfs(visited, map, next, target)) return true;
            }
        }
        return false;
    }

深度优先搜索和题目总结

DFS