刷题（13） DFS &BFS & Backtracking

BFS 常用在算最短路径

backtracking通常是排列，组合，选择类问题

695. Max Area of Island 和547. Number of Provinces 很像，都是DFS，岛屿问题，就是要先弄清楚是什么个相连法，比如695是模拟成小方块四个边相连，547则是无方向节点相连。

46. Permutations  backtracking, 思路就是每一位都试一遍所有数，先定第一位，再定第二位，这样。所以time complexity: O(n*n!), space complex O(n!)

class Solution {

    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> list = new ArrayList<>();

        if(nums.length<1) return list;

        getList(nums, list, new ArrayList<Integer>());

        return list;

    }

    private void getList(int[] nums, List<List<Integer>> list, List<Integer> temp) {

        if(temp.size() == nums.length) {

            list.add(new ArrayList<>(temp)); /// 注意这里！！！！！不要直接add temp！

            return;

        }

        for(int i=0;i<nums.length;i++){

            if(temp.contains(nums[i]))

                    continue;

            temp.add(nums[i]);

            getList(nums, list, temp);

            temp.remove(temp.size()-1);

        }

    }

}

47. Permutations II 就是46的基础上再加每个数字都可以重复。 方法差不多，就是得去重。有看到三种解法。1. 用map记录每个数字出现的次数，然后根据map来构建permutation 2. 排序，然后swap 3. set去重最后结果，used用来记录一个地方是不是visit过

77. Combinations和46差不多，不过77不要考虑重复值，[1,2][2,1]算一种

40. Combination Sum II 39. Combination Sum 216. Combination Sum III， 无非就是能不能重复值，变一变取值集什么的。不能重复值的话感觉用sort先拍下序再取值比较好，比如40， 因为这个是是否pick的问题，而不是所有值的组合比如77.

79. Word Search 也是backtracking，这个要注意是最后才清空visited值，以免影响下一个值为起点的判断。

51. N-Queens 是hard！backtracking, 这里比较难的是如何构建这个数据结构，如何去做BACKTRACKING, 然后diagonal和antidiagonal是可以根据row&col来构建的。

934. Shortest Bridge 可以用DFS或者BFS来找到第一个岛屿，然后用BFS找到与第二个岛屿的最短路径。