1. 全排列

1. 特点

需要visited判断重复搜索
长度一致时出口
从0开始遍历，遍历过程中进行判断重复搜索和去重
visited[i]重置
回溯剪枝

2. 题目

全排列，无重复：https://leetcode-cn.com/problems/permutations/

class Solution {
 List<List<Integer>> result = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 public List<List<Integer>> permute(int[] nums) {
     //全排列无重复
     //出口：list长度和nums一致时
     //从0开始遍历，需要visited判断重复搜索
     if(nums.length == 0){
         return result;
     }

     boolean[] visited = new boolean[nums.length];
     dfs(nums,visited);
     return result;
 }

 public void dfs(int[] nums,boolean[] visited){
     //出口
     if(list.size() == nums.length){
         result.add(new ArrayList<>(list));
         return;
     }

     //从0开始遍历
     for(int i=0;i<nums.length;i++){
         //重复搜索判断
         if(visited[i]){
             continue;
         }
         list.add(nums[i]);
         visited[i] = true;
         dfs(nums,visited);
         visited[i] = false;
         //回溯剪枝
         list.remove(list.size()-1);
     }
 }
}

全排列，有重复：https://leetcode-cn.com/problems/permutations-ii/submissions/

class Solution {
 List<List<Integer>> result = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 public List<List<Integer>> permuteUnique(int[] nums) {
     //全排列有重复，先排序，遍历过程中去重
     if(nums.length == 0){
         return result;
     }
     Arrays.sort(nums);
     boolean[] visited = new boolean[nums.length];
     dfs(nums,visited);
     return result;
 }

 public void dfs(int[] nums,boolean[] visited){
     //出口
     if(list.size() == nums.length){
         result.add(new ArrayList<>(list));
         return;
     }

     //从0开始遍历
     for(int i=0;i<nums.length;i++){
         if(visited[i]){
             continue;
         }
         //前一个已经匹配，有重复
         if(i>0 && nums[i]==nums[i-1] && visited[i-1]){
             continue;
         }
         list.add(nums[i]);
         visited[i] = true;
         dfs(nums,visited);
         visited[i] = false;
         list.remove(list.size()-1);
     }
 }
}

字符串排序：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/submissions/

class Solution {
 List<String> result = new ArrayList<>();
 public String[] permutation(String s) {
     //字符串全排列，先排序，需要visited，从0开始遍历
     char[] str = s.toCharArray();
     Arrays.sort(str);
     boolean[] visited = new boolean[str.length];
     //初始temp字符串为空
     dfs(str,visited,"");
     return result.toArray(new String[result.size()]);
 }

 public void dfs(char[] str,boolean[] visited,String temp){
     if(temp.length() == str.length){
         result.add(temp);
         return;
     }

     //从0开始遍历
     for(int i=0;i<str.length;i++){
         if(visited[i]){
             continue;
         }
         if(i>0 && str[i]==str[i-1] && visited[i-1]){
             continue;
         }
         visited[i] = true;
         dfs(str,visited,temp+str[i]);
         visited[i] = false;
     }
 }
}

电话号码组合(全排列)：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/

class Solution {
 //Map存放九宫格的数字和字母对应的kv
 Map<Character,String> map = new HashMap<>();
 List<String> result = new ArrayList<>();
 String digits;
 public List<String> letterCombinations(String digits) {
     this.digits = digits;
     if(digits.length() == 0){
         return result;
     }
     //预存kv
     map.put('2', "abc");
     map.put('3', "def");
     map.put('4', "ghi");
     map.put('5', "jkl");
     map.put('6', "mno");
     map.put('7', "pqrs");
     map.put('8', "tuv");
     map.put('9', "wxyz");

     dfs(0,"");
     return result;
 }

 public void dfs(int index,String temp){
     //出口，当temp长度等于digits时
     if(temp.length() == digits.length()){
         result.add(temp);
         return;
     }

     //提取当前数字对应的字符串
     String str = map.get(digits.charAt(index));

     for(int i=0;i<str.length();i++){
         dfs(index+1,temp+str.charAt(i));
     }
 }
}

括号生成：https://leetcode-cn.com/problems/generate-parentheses/submissions/

class Solution {
 List<String> result = new ArrayList<>();
 public List<String> generateParenthesis(int n) {
     //全排列，从n,n往左右两边扩散

     dfs(n,n,"");
     return result;
 }

 public void dfs(int left,int right,String temp){
     if(left == 0 && right == 0){
         result.add(temp);
         return;
     }

     if(left > 0){
         dfs(left-1,right,temp+"(");
     }
     if(right > left){
         dfs(left,right-1,temp+")");
     }
 }
}

2. 子集

1. 特点

从0开始递归
如果有重复，先排序，遍历时去重
不需要出口，直接添加层存储
从i开始遍历
回溯剪枝

2. 题目

子集：https://leetcode-cn.com/problems/subsets/submissions/

class Solution {
 List<List<Integer>> result = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 public List<List<Integer>> subsets(int[] nums) {
     //子集，直接添加不需要出口，从i开始遍历
     if(nums.length == 0){
         return result;
     }

     dfs(nums,0);
     return result;
 }

 public void dfs(int[] nums,int index){
     result.add(new ArrayList<>(list));

     for(int i=index;i<nums.length;i++){
         list.add(nums[i]);
         dfs(nums,i+1);
         list.remove(list.size()-1);
     }
 }
}

子集(有重复):https://leetcode-cn.com/problems/subsets-ii/submissions/

class Solution {
 List<List<Integer>> result = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 public List<List<Integer>> subsetsWithDup(int[] nums) {
     //子集有重复，先排序，遍历时进行去重
     if(nums.length == 0){
         return result;
     }
     Arrays.sort(nums);
     dfs(0,nums);
     return result;
 }

 public void dfs(int index,int[] nums){
     result.add(new ArrayList<>(list));

     for(int i=index;i<nums.length;i++){
         if(i>index && nums[i]==nums[i-1]){
             continue;
         }
         list.add(nums[i]);
         dfs(i+1,nums);
         list.remove(list.size()-1);
     }
 }
}

3. 组合总和

1. 特点

如果是组合，确定出口和可用元素
如果是总和，先排序进行递减，如果无重复，遍历时不用去重。如果有重复，遍历时要进行去重
从0开始递归
出口：目标值递减到0
从index开始遍历，判断target-nums[i]是否小于0，break
去重
添加、递归、回溯剪枝

2. 题目

组合：https://leetcode-cn.com/problems/combinations/

class Solution {
 List<Integer> list = new ArrayList<>();
 List<List<Integer>> result = new ArrayList<>();
 public List<List<Integer>> combine(int n, int k) {
     //出口：list长度为k
     //可用元素：从1到n

     dfs(1,n,k);
     return result;
 }

 public void dfs(int start,int end,int k){
     if(list.size() == k){
         result.add(new ArrayList<>(list));
         return;
     }

     for(int i=start;i<=end;i++){
         list.add(i);
         dfs(i+1,end,k);
         list.remove(list.size()-1);
     }
 }
}

组合：https://leetcode-cn.com/problems/combination-sum-iii/

class Solution {
 List<List<Integer>> result = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 public List<List<Integer>> combinationSum3(int k, int n) {
     //出口：n递减到0，list长度为k
     //可用元素：1到9

     dfs(1,n,k);
     return result;
 }

 public void dfs(int start,int n,int k){
     if(n == 0 && list.size() == k){
         result.add(new ArrayList<>(list));
         return;
     }

     for(int i=start;i<=9;i++){
         list.add(i);
         dfs(i+1,n-i,k);
         list.remove(list.size()-1);
     }
 }
}

组合总和（无重复，元素可以用多次）：https://leetcode-cn.com/problems/combination-sum/submissions/

class Solution {

 List<List<Integer>> result = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 public List<List<Integer>> combinationSum(int[] candidates, int target) {
     //类型：dfs组合总和
     //思路：
     //1. 递归出口：target递减到0
     //2. 从index开始遍历，需要递减，先排序
     //3. 遍历时判断是否溢出

     Arrays.sort(candidates);
     dfs(candidates,target,0);

     return result;
 }

 public void dfs(int[] candidates,int target,int index){
     if(target == 0){
         result.add(new ArrayList<>(list));
         return;
     }

     for(int i=index;i<candidates.length;i++){
         if(target - candidates[i] < 0){
             break;
         }
         list.add(candidates[i]);
         dfs(candidates,target-candidates[i],i);
         list.remove(list.size()-1);
     }
 }
}

组合总和（有重复，元素只能用1次）：https://leetcode-cn.com/problems/combination-sum-ii/submissions/

class Solution {
 List<List<Integer>> result = new ArrayList<>();
 List<Integer> list = new ArrayList<>();
 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
     //总和，先排序，遍历时递减顺便去重
     //出口：target递减到0
     //从index开始遍历
     if(candidates.length == 0){
         return result;
     }
     Arrays.sort(candidates);
     dfs(candidates,target,0);
     return result;
 }

 public void dfs(int[] candidates,int target,int index){
     if(target == 0){
         result.add(new ArrayList<>(list));
         return;
     }

     for(int i=index;i<candidates.length;i++){
         if(target - candidates[i] < 0){
             break;
         }
         if(i > index && candidates[i]==candidates[i-1]){
             continue;
         }
         list.add(candidates[i]);
         dfs(candidates,target-candidates[i],i+1);
         list.remove(list.size()-1);
     }
 }
}

4. 二维

岛屿周长：https://leetcode-cn.com/problems/island-perimeter/submissions/

class Solution {
 public int islandPerimeter(int[][] grid) {
     if(grid.length == 0 || grid[0].length == 0){
         return 0;
     }
     for(int i=0;i<grid.length;i++){
         for(int j=0;j<grid[0].length;j++){
             if(grid[i][j] == 1){
                 return dfs(i,j,grid);
             }
         }
     }
     return 0;
 }

 public int dfs(int row,int col,int[][] grid){
     //1出口，遇到0时，周长+1，返回1
     if(row < 0 || row > grid.length-1 || col < 0 || col > grid[0].length-1 || grid[row][col] == 0){
         return 1;
     }
     //0出口，已经搜索过了
     if(grid[row][col] == 2){
         return 0;
     }
     grid[row][col] = 2;
     return dfs(row+1,col,grid) + dfs(row-1,col,grid) + dfs(row,col+1,grid) + dfs(row,col-1,grid);
 }
}

岛屿数量:https://leetcode-cn.com/problems/number-of-islands/submissions/

class Solution {
 public int numIslands(char[][] grid) {
     if(grid.length == 0 || grid[0].length == 0){
         return 0;
     }
     int result = 0;
     for(int i=0;i<grid.length;i++){
         for(int j=0;j<grid[0].length;j++){
             if(grid[i][j] == '1'){
                 dfs(i,j,grid);
                 result++;
             }
         }
     }
     return result;
 }

 public void dfs(int row,int col,char[][] grid){
     //出口
     if(row < 0 || row > grid.length-1 || col < 0 || col > grid[0].length-1 || grid[row][col] == '0'){
         return;
     }
     //表示已经搜索过了
     grid[row][col] = '0';
     //搜索上下左右
     dfs(row+1,col,grid);
     dfs(row-1,col,grid);
     dfs(row,col+1,grid);
     dfs(row,col-1,grid);
 }
}

岛屿面积：https://leetcode-cn.com/problems/max-area-of-island/submissions/

class Solution {
 public int maxAreaOfIsland(int[][] grid) {
     if(grid.length == 0 || grid[0].length == 0){
         return 0;
     }
     int result = 0;
     for(int i=0;i<grid.length;i++){
         for(int j=0;j<grid[0].length;j++){
             //当矩阵为1时，进行dfs，提取最大值
             if(grid[i][j] == 1){
                 result = Math.max(dfs(i,j,grid),result);
             }
         }
     }
     return result;
 }

 public int dfs(int row,int col,int[][] grid){
     //0出口
     if(row > grid.length-1 || row < 0 || col > grid[0].length-1 || col < 0 || grid[row][col] == 0){
         return 0;
     }
     //修改为0
     grid[row][col] = 0;
     //叠加上下左右
     return 1 + dfs(row+1,col,grid) + dfs(row-1,col,grid) + dfs(row,col+1,grid) + dfs(row,col-1,grid);
 }
}

朋友圈：https://leetcode-cn.com/problems/friend-circles/submissions/

class Solution {
 public int findCircleNum(int[][] M) {

     if(M.length == 0 || M[0].length == 0){
         return 0;
     }

     boolean[] visited = new boolean[M.length];
     int result = 0;
     for(int i=0;i<M.length;i++){
         //未被搜索
         if(visited[i] == false){
             dfs(i,visited,M);
             result++;
         }
     }
     return result;
 }

 public void dfs(int row,boolean[] visited,int[][] M){
     for(int i=0;i<M[0].length;i++){
         if(visited[i] == false && M[row][i] == 1){
             visited[i] = true;
             dfs(i,visited,M);
         }
     }
 }
}

单词搜索：https://leetcode-cn.com/problems/word-search/submissions/

class Solution {
 public boolean exist(char[][] board, String word) {
     //搜索矩阵，不使用额外空间，保存当前位置字符，dfs之后恢复
     int row = board.length;
     int col = board[0].length;

     for(int i=0;i<board.length;i++){
         for(int j=0;j<board[0].length;j++){
             if(dfs(i,j,board,word,0)){
                 return true;
             }
         }
     }
     return false;
 }

 public boolean dfs(int row,int col,char[][] board,String word,int index){
     //false出口
     if(row < 0 || col < 0 || row > board.length-1 || col > board[0].length-1 || board[row][col] != word.charAt(index)){
         return false;
     }

     //true出口
     if(index == word.length()-1){
         return true;
     }

     char temp = board[row][col];
     board[row][col] = '/';
     boolean result = dfs(row+1,col,board,word,index+1) || dfs(row-1,col,board,word,index+1) || dfs(row,col+1,board,word,index+1) || dfs(row,col-1,board,word,index+1);
     board[row][col] = temp;
     return result;
 }
}

机器人的运动范围：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

class Solution {
 int result = 0;
 public int movingCount(int m, int n, int k) {
     //从[0,0]到[m,n]，需要visited判断重复搜索
     boolean[][] visited = new boolean[m][n];
     dfs(0,0,m,n,k,visited);
     return result;
 }

 public void dfs(int i,int j,int row,int col,int k,boolean[][] visited){
     //继续递归
     if(i<row && j<col && (i%10+i/10 + j%10+j/10) <= k && visited[i][j] == false){
         result++;
         visited[i][j] = true;
         dfs(i+1,j,row,col,k,visited);
         dfs(i,j+1,row,col,k,visited);
     }
 }
}

DFS + 回溯

1. 全排列

1. 特点

2. 题目

2. 子集

1. 特点

2. 题目

3. 组合总和

1. 特点

2. 题目

4. 二维