题目列表

组合

77. 组合（中等）
17. 电话号码的字母组合（中等）
39. 组合总和（中等）
40. 组合总和 II（中等）
216. 组合总和 III

分割
93. 复原 IP 地址（中等）
131. 分割回文串

子集
78. 子集（中等）
90. 子集 II（中等）：剪枝技巧同 47 题、39 题、40 题；

排列
46. 全排列（中等）
47. 全排列 II（中等）：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；
60. 第 k 个排列（中等）：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；

Flood Fill
733. 图像渲染（Flood Fill，中等）
200. 岛屿数量（中等）
130. 被围绕的区域（中等）
79. 单词搜索（中等）

字符串中的回溯问题
784. 字母大小写全排列（中等）
22. 括号生成（中等）:这道题广度优先遍历也很好写，可以通过这个问题理解一下为什么回溯算法都是深度优先遍历，并且都用递归来写。

游戏问题
51. N 皇后（困难）：其实就是全排列问题，注意设计清楚状态变量，在遍历的时候需要记住一些信息，空间换时间；
37. 解数独（困难）：思路同「N 皇后问题」；
488. 祖玛游戏（困难）

具体实现

组合

77. 组合

class Solution {
  List<List<Integer>> res;
  public void dfs(int level, int start, ArrayList path, int n, int k){
      if(level == k){
          res.add(new ArrayList(path));
          return;
      }
      for(int i = start; i <= n; i++){
              path.add(i);
              dfs(level + 1, i + 1, path, n, k);
              path.remove(path.size() - 1);
      }
  }
  public List<List<Integer>> combine(int n, int k) {
      res = new ArrayList<>();
      ArrayList<Integer> path = new ArrayList<>();
      dfs(0, 1, path, n, k);
      return res;
  }
}

17. 电话号码的字母组合

class Solution {
  List<String> res;
  String[] snum= new String[]{
      "","",
      "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
  };
  public void dfs(int level, String digits, String path){
      if(level == digits.length()){
          res.add(path);
          return;
      }
      int t = digits.charAt(level) - '0';
      String tmp = snum[t];
      for(int i = 0; i < tmp.length(); i++){
          dfs(level + 1, digits, path + tmp.charAt(i));
      }
  }
  public List<String> letterCombinations(String digits) {
      res = new ArrayList<>();
      if(digits.length() == 0) return res;
      String path = "";
      dfs(0, digits, path);
      return res;
  }
}

39. 组合总和（中等）

class Solution {
  List<List<Integer>> res;
  public void dfs(int start, int sum, ArrayList path, int[] candidates, int target){
      if(sum >= target){
          if(sum == target) res.add(new ArrayList(path));
          return;
      }
      for(int i = start; i < candidates.length; i++){
          path.add(candidates[i]);
          dfs(i, sum + candidates[i], path, candidates, target);
          path.remove(path.size() - 1);
      }
  }
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
      res = new ArrayList<>();
      ArrayList path = new ArrayList<>();
      dfs(0, 0, path, candidates, target);
      return res;
  }
}

40. 组合总和 II（中等）

class Solution {
  List<List<Integer>> res;
  public void dfs(int start, int sum, ArrayList path, int[] candidates, int target){
      if(sum >= target){
          if(sum == target) res.add(new ArrayList(path));
          return;
      }
      for(int i = start; i < candidates.length; i++){
          if(i > start && candidates[i] == candidates[i - 1]) continue;
          path.add(candidates[i]);
          dfs(i + 1, sum + candidates[i], path, candidates, target);
          path.remove(path.size() - 1);
      }
  }
  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      res = new ArrayList<>();
      Arrays.sort(candidates);
      ArrayList path = new ArrayList<>();
      dfs(0, 0, path, candidates, target);
      return res;
  }
}

216. 组合总和 III

class Solution {
  int[] choose = new int[]{1,2,3,4,5,6,7,8,9};
  List<List<Integer>> res;
  public void dfs(int level, int start, int sum, int k, int n, ArrayList path){
      if(level == k){
          if(sum == n) res.add(new ArrayList(path));
          return;
      }
      for(int i = start; i < choose.length; i++){
          path.add(choose[i]);
          dfs(level + 1, i + 1, sum + choose[i], k, n, path);
          path.remove(path.size() - 1);
      }
  }
  public List<List<Integer>> combinationSum3(int k, int n) {
      res = new ArrayList<>();
      ArrayList<Integer> path = new ArrayList<>();
      dfs(0, 0, 0, k, n, path);
      return res;
  }
}

排列

46. 全排列

class Solution {
  List<List<Integer>> res;
  boolean[] f;
  public void dfs(int level, int[] nums, ArrayList path){
      if(level == nums.length){
          /*
          如果直接res.add(path);会发现res里面全部都是空的列表对象
          变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，
          深度优先遍历完成以后，回到了根结点，成为空列表。
          在 Java 中，参数传递是值传递，对象类型变量在传参的过程中，复制的是变量的地址。
          这些地址被添加到res变量，但实际上指向的是同一块内存地址，
          因此我们会看到空的列表对象。解决的方法很简单,这里做一次拷贝即可。
          */
          res.add(new ArrayList(path));
          return;
      }
      for(int i = 0; i < nums.length; i++){
          if(f[i] == false){
              f[i] = true;
              path.add(nums[i]);
              dfs(level + 1, nums, path);
              f[i] = false;
              path.remove(path.size() - 1);
          }
      }
  }
  public List<List<Integer>> permute(int[] nums) {
      res = new ArrayList<>();
      f = new boolean[nums.length];
      ArrayList path = new ArrayList<>();
      dfs(0, nums, path);
      return res;
  }
}

47. 全排列 II（中等）

if(i > 0 && nums[i] == nums[i - 1] && f[i - 1] == false) continue;

如果这个数和之前的数一样，并且之前的数还未使用过，说明当前的这种情况已经回溯过了，为了避免重复就可以跳过

class Solution {
  List<List<Integer>> res;
  boolean[] f;
  public void dfs(int level, int[] nums, ArrayList path){
      if(level == nums.length){
          res.add(new ArrayList(path));
          return;
      }
      for(int i = 0; i < nums.length; i++){
          if(f[i] == false){
              if(i > 0 && nums[i] == nums[i - 1] && f[i - 1] == false) continue;
              f[i] = true;
              path.add(nums[i]);
              dfs(level + 1, nums, path);
              f[i] = false;
              path.remove(path.size() - 1);
          }
      }
  } 
  public List<List<Integer>> permuteUnique(int[] nums) {
      res = new ArrayList<>();
      f = new boolean[nums.length];
      ArrayList<Integer> path = new ArrayList<>();
      Arrays.sort(nums);
      dfs(0, nums, path);
      return res;
  }
}

Flood Fill

200. 岛屿数量

class Solution {
  int res = 0;
  int[] dx = new int[]{-1, 1, 0, 0};
  int[] dy = new int[]{0, 0, -1, 1};
  public void dfs(int i, int j, char[][] grid){
      grid[i][j] = '0';
      for(int x = 0; x < 4; x++){
          int a = i + dx[x];
          int b = j + dy[x];
          if(a >= 0 && a < grid.length && b >= 0 && b < grid[0].length && grid[a][b] == '1'){
              dfs(a, b, grid);
          }
      }
  }
  public int numIslands(char[][] grid) {
      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);
                  res++;
              }
          }
      }
      return res;
  }
}

130. 被围绕的区域

从四周开始突围，突围成功的标记成’.‘，突围失败的最后变成x

class Solution {
  int[] dx = new int[]{-1, 1, 0, 0};
  int[] dy = new int[]{0, 0, -1, 1};
  public void dfs(int i, int j, char[][] board){
      board[i][j] = '.';
      for(int x = 0; x < 4; x++){
          int a = i + dx[x];
          int b = j + dy[x];
          if(a >= 0 && a < board.length && b >= 0 && b < board[0].length && board[a][b] == 'O'){
              dfs(a, b, board);
          }
      }
  }
  public void solve(char[][] board) {
      int m = board.length;
      int n = board[0].length;
      for(int i = 0; i < m; i++){
          if(board[i][0] == 'O') dfs(i, 0, board);
          if(board[i][n - 1] == 'O') dfs(i, n - 1, board);
      }
      for(int i = 0; i < n; i++){
          if(board[0][i] == 'O') dfs(0, i, board);
          if(board[m-1][i] == 'O') dfs(m - 1, i, board);
      }
      for(int i = 0; i < m; i++){
          for(int j = 0; j < n; j++){
              //救不回来的兄弟，就变成x了
              if(board[i][j] == 'O') board[i][j] = 'X';
              //救回来的兄弟，恢复成o
              if(board[i][j] == '.') board[i][j] = 'O';
          }
      }
  }
}

回溯

题目列表

组合

分割

子集

排列

Flood Fill

字符串中的回溯问题

游戏问题

具体实现

组合

排列

Flood Fill