刷题笔记之回溯（下）

子集问题

LeetCode 78. 子集

LeetCode题目链接

• 前面的组合问题和分割问题都是收集叶子节点，而子集问题是收集所有结点。
• 子集是无序的，在集合[1,2,3]中，[1,2]和[2,1]是一样的。
• 为了避免重复，for就要从start开始，而不是从0开始。
• 树状图
  

回溯三部曲：

• 确定回溯函数参数

  List<List<Integer>> res = new ArrayList<>();
  List<Integer> tmp = new ArrayList<>();
  
  private void backtrack(int[] nums, int start)

• 确定终止条件

  //当集合为空，即start已经大于数组长度就停止遍历
  if (start >= nums.length) {
      return;
  }

  也可以直接 res.add(new ArrayList(tmp))，本题就是将所有结点加入结果集。

• 确定单层循环逻辑

  for(int i = start; i < nums.length; i++){
      tmp.add(nums[i]);
      backtrack(nums, i + 1);
      tmp.remove(tmp.size() - 1);
  }

• 完整代码

  class Solution {
      List<List<Integer>> res = new ArrayList<>();
      List<Integer> tmp = new ArrayList<>();
  
      public List<List<Integer>> subsets(int[] nums) {
          if (nums.length == 0) {
              return res;
          }
          backtrack(nums, 0);
          return res;
      }
  
      private void backtrack(int[] nums, int start) {
          res.add(new ArrayList(tmp));
          for (int i = start; i < nums.length; i++) {
              tmp.add(nums[i]);
              backtrack(nums, i + 1);
              tmp.remove(tmp.size() - 1);
          }
      }
  }

LeetCode 90. 子集 II

LeetCode题目链接

在78. 子集规定了数组中的元素 互不相同，倘若出现[1,2,2]这样的集合，那么结果集中就会有两个[1,2]，因为两个2虽然值相同，但它们在数组中所处的位置不同，要解决这个问题，就需要用到40. 组合总和II中去重的方法,为了使重复元素相邻，我们依然要对数组进行排序。

//对原始数组排序使得重复元素集中在一起
Arrays.sort(candidates);
//定义一个used数组记录此某元素是否被访问过
 if(i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]){
            continue;
    }

回溯三部曲：

• 确定回溯函数参数

  List<List<Integer>> res = new ArrayList<>();
  List<Integer> tmp = new ArrayList<>();
  boolean[] used;
  
  private void backtrack(int[] nums, int start)

• 确定终止条件
  与上题相同，只需要res.add(new ArrayList(tmp));即可。

• 确定单层循环逻辑
  其实与40. 组合总和 II的代码大差不差。
  

  for(int i = start; i < nums.length; i++){
      if(i > 0 && nums[i - 1] == nums[i] && !used[i - 1]){
          continue;
      }
      tmp.add(nums[i]);
      used[i] = true;
      backtrack(nums, i + 1);
      tmp.remove(tmp.size() - 1);
      used[i] = false;
  }

• 完整代码

  class Solution {
      List<List<Integer>> res = new ArrayList<>();
      List<Integer> tmp = new ArrayList<>();
      boolean[] used;
  
      public List<List<Integer>> subsetsWithDup(int[] nums) {
          if (nums.length == 0) {
              return res;
          }
          used = new boolean[nums.length];
          Arrays.fill(used, false);
          Arrays.sort(nums);
          backtrack(nums, 0);
          return res;
      }
  
      private void backtrack(int[] nums, int start) {
          res.add(new ArrayList(tmp));
          for (int i = start; i < nums.length; i++) {
              if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
                  continue;
              }
              tmp.add(nums[i]);
              used[i] = true;
              backtrack(nums, i + 1);
              tmp.remove(tmp.size() - 1);
              used[i] = false;
          }
      }
  }

LeetCode 491. 递增子序列

LeetCode题目链接
本题有几个细节需要注意：

• 递增子序列中 至少有两个元素，即不止在叶子节点收集结果，只要有两个符合条件就可以加入结果集不止在叶子节点收集结果，可以抽象为子集问题。

• 两数相等也视为递增。

• 1 <= nums.length <= 15，*-100 <= nums[i] <= 100*，数组长度不大且元素值也不大，可以开辟辅助数组 visited 帮助记录。

• 树状图如下：
  
  回溯三部曲：

• 确定回溯函数参数

  List<List<Integer>> res = new ArrayList<>();
  List<Integer> tmp = new ArrayList<>();
  
  private void backtrack(int[] nums, int start)

• 确定终止条件

  //只要有两个符合条件就可以加入结果集
  if(tmp.size() >= 2){
      res.add(new ArrayList(tmp));
      return;
  }

• 确定单层循环逻辑

  //局部变量，只记录本层递归有没有重复元素,下一层递归重新创建
  int[] visited = new int[201];
  for(int i = start; i < nums.length; i++){
      /*
      !tmp.isEmpty():防止异常
      nums[i] < tmp.get(tmp.size() - 1)：当前数是否小于临时集合中最后一个数
      visited[nums[i] + 100] == 1：是否访问过此数
      */
      if((!tmp.isEmpty() && nums[i] < tmp.get(tmp.size() - 1)) || visited[nums[i] + 100] == 1){
          continue;
      }
      tmp.add(nums[i]);
      /*
      nums[i] = 10,visited[110] = 1,如果下次再遇到10就会直接continue
      */
      visited[nums[i] + 100] = 1;
      backtrack(nums, i + 1);
      tmp.remove(tmp.size() - 1);
      // visited[nums[i] + 100] = 0;所以这里不用再对visit回溯
  }

  也可以使用map去重：

  for (int i = start; i < nums.length; i++) {
      if (!tmp.isEmpty() && nums[i] < tmp.get(tmp.size() - 1)) {
          continue;
      }
      // 使用过了当前数字
      if (map.getOrDefault(nums[i], 0) >= 1) {
          continue;
      }
      //每拿到一个数就放入map中
      map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
      tmp.add(nums[i]);
      backtrack(nums, i + 1);
      tmp.remove(tmp.size() - 1);
  }

• 完整代码

  class Solution {
      List<List<Integer>> res = new ArrayList<>();
      List<Integer> tmp = new ArrayList<>();
  
      public List<List<Integer>> findSubsequences(int[] nums) {
          if (nums.length == 0) {
              return res;
          }
          backtrack(nums, 0);
          return res;
      }
  
      private void backtrack(int[] nums, int start) {
          if (tmp.size() >= 2) {
              res.add(new ArrayList(tmp));
              return;
          }
  
          int[] visited = new int[201];//局部变量，只记录本层递归有没有重复元素
          for (int i = start; i < nums.length; i++) {
              if ((!tmp.isEmpty() && nums[i] < tmp.get(tmp.size() - 1)) || visited[nums[i] + 100] == 1) {
                  continue;
              }
              tmp.add(nums[i]);
              visited[nums[i] + 100] = 1;
              backtrack(nums, i + 1);
              tmp.remove(tmp.size() - 1);
              // visited[nums[i] + 100] = 0;所以这里不用再对visit回溯
          }
      }
  }

排列问题

LeetCode 46. 全排列

LeetCode题目链接
树状图：

回溯三部曲：

• 确定回溯函数参数
  排列问题主要的区别在于集合内元素是有序的，[1,2]和[2,1]是两个不同的集合，如果我先取了2，那就还要倒回去再取1，所以不需要使用start。
  如果已经取到[2,1]，为了保证不重复取到2，就需要一个used数组来标记已经取过的元素。

  List<List<Integer>> res = new ArrayList<>();
  List<Integer> tmp = new ArrayList<>();
  boolean[] used; 
  
  private void backtrack(int[] nums)

• 确定终止条件

  //由树状图可以清晰的得到，当数组遍历到叶子节点，即tmp的长度等于数组长度时就加入结果集
  if(tmp.size() == nums.length){
      res.add(new ArrayList(tmp));
      return;
  }

• 确定单层循环逻辑

  for(int i = 0; i < nums.length; i++){
      //如果当前元素已经取过，就跳过继续取下一个
      if(used[i]){
          continue;
      }
      tmp.add(nums[i]);
      used[i] = true;
      backtrack(nums);
      tmp.remove(tmp.size() - 1);
      used[i] = false;
  }

• 完整代码

  class Solution {
      List<List<Integer>> res = new ArrayList<>();
      List<Integer> tmp = new ArrayList<>();
      boolean[] used; 
      public List<List<Integer>> permute(int[] nums) {
          used = new boolean[nums.length];
          Arrays.fill(used, false);
          backtrack(nums);
          return res;
      }
      /*
      和组合问题不同，可以取前面的数字！
      i从0开始，之前从start开始为了防止取到前面的数，排列问题可以取前面的数，用used控制数是否取过
      */
      private void backtrack(int[] nums){
          if(tmp.size() == nums.length){
              res.add(new ArrayList(tmp));
              return;
          }
  
          for(int i = 0; i < nums.length; i++){
              if(used[i]){
                  continue;
              }
              tmp.add(nums[i]);
              used[i] = true;
              backtrack(nums);
              tmp.remove(tmp.size() - 1);
              used[i] = false;
          }
      }
  }

LeetCode 47. 全排列 II

LeetCode题目链接
参考40. 组合总和II和90. 子集II一样的套路,不同点是本题需要做树枝去重。
为什么要做树枝去重？
本质上还是为了防止一轮循环中拿到重复的元素，之前的去重都有 start 不断更新起点，used也是一样的，如果这个元素这轮访问过了，那么下一轮就不要在访问了。

if(i > 0 && nums[i - 1] == nums[i] && !used[i - 1]){//树层去重
    continue;
}
if(used[i]){//树枝去重
    continue;
}

剩下的地方没什么区别，直接上完整代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> tmp = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0) {
            return res;
        }
        used = new boolean[nums.length];
        //对原始数组排序，使得重复元素相邻便于去重
        Arrays.sort(nums);
        backtrack(nums);
        return res;
    }

    //去重！！！！！！！
    private void backtrack(int[] nums) {
        if (tmp.size() == nums.length) {
            res.add(new ArrayList(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {//树层去重
                continue;
            }
            if (used[i]) {//树枝去重
                continue;
            }
            tmp.add(nums[i]);
            used[i] = true;
            backtrack(nums);
            tmp.removeLast();
            used[i] = false;
        }
    }
}

上上强度

LeetCode 51. N 皇后

LeetCode题目链接
N皇后的约束条件：

• 不能处在同一行

• 不能处在同一列

• 不能处在同一斜线
  树状图如下：
  
  这三个条件不难写出一个判断皇后位置是否合法的方法：

  private boolean isValid(int row, int col, int n, char[][] board){
      //是否处在同一列
      for(int i = 0; i < row; i++){
          if(board[i][col] == 'Q'){
              return false;
          }
      }
      //是否处在45°斜线
      for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
          if(board[i][j] == 'Q'){
              return false;
          }
      }
      //是否处在135°斜线
      for(int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++){
          if(board[i][j] == 'Q'){
              return false;
          }
      }
  
      return true;
  }

  回溯三部曲：

• 确定回溯函数参数

  List<List<String>> res = new ArrayList<>();
  /*
  n: 皇后个数
  row: 遍历到了第几行
  board: 棋盘
  */
  private void backtrack(int n, int row, char[][] board)

• 确定终止条件

  //只要搜索到叶子节点，代表最后一个皇后已经放下，将当前棋盘放入结果集
  if(row == n){
      res.add(charToString(board));
      return;
  }

• 确定单层循环逻辑

  for(int i = 0; i < n; i++){
      //检查当前位置是否合法
      if(isValid(row, i, n, board)){
          board[row][i] = 'Q';
          backtrack(n, row + 1, board);
          board[row][i] = '.';
      }
  }

• 完整代码

class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        if (n == 0) {
            return res;
        }

        char[][] board = new char[n][n];

        for (char[] c : board) {
            Arrays.fill(c, '.');
        }

        backtrack(n, 0, board);

        return res;
    }

    private void backtrack(int n, int row, char[][] board) {
        if (row == n) {
            res.add(charToString(board));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isValid(row, i, n, board)) {
                board[row][i] = 'Q';
                backtrack(n, row + 1, board);
                board[row][i] = '.';
            }
        }
    }

    private List charToString(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] c : board) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    private boolean isValid(int row, int col, int n, char[][] board) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
}

LeetCode 37. 解数独

LeetCode题目链接
数独的约束条件：

• 1-9每行只能出现一次

• 1-9每列只能出现一次

• 1-9每个九宫格内只能出现一次
  由这三个条件能写出一个判断当前位置是否合法的方法：

  private boolean isValid(int row, int col, char k, char[][] board){
      //是否在同一行
      for(int i = 0; i < 9; i++){
          if(board[row][i] == k){
              return false;
          }
      }
      //是否在同一列
      for(int i = 0; i < 9; i++){
          if(board[i][col] == k){
              return false;
          }
      }
      /*
      startRow和startCol用来计算每个九宫格的起始位置
      9个九宫格占3行，每行有3个，row / 3 * 3得到行标
      9个九宫格占3列，每列有3个，col / 3 * 3得到列标
      */
      int startRow = row / 3 * 3;
      int startCol = col / 3 * 3;
      //是否在同一个九宫格内
      for(int i = startRow; i < startRow + 3; i++){
          for(int j = startCol; j < startCol + 3; j++){
              if(board[i][j] == k){
                  return false;
              }
          }
      }
      return true;
  }

  回溯三部曲：

• 确定回溯函数参数

  //本题不需要返回值
  private boolean backtrack(char[][] board)

• 如果遇到无解数独会不会死循环？
  答案是不会，最内层循环一轮走完只会出现两种结果，要么填了一个合法的数，要么发现9个数都不合法，当退出循环时就返回false了。

• 确定终止条件
  本题递归不用终止条件，遍历整个树形结构寻找可能的叶子节点就立刻返回。

• 确定单层递归逻辑

  //搜索树层用void,搜索树枝用booealn
  private boolean backtrack(char[][] board){
      for(int i = 0; i < board.length; i++){
          for(int j = 0; j < board[0].length; j++){
              if(board[i][j] == '.'){
                  for(char k = '1'; k <='9'; k++){
                      if(isValid(i, j, k, board)){
                          board[i][j] = k;
                          boolean res = backtrack(board);
                          if(res){//找到结果立刻返回
                              return true;
                          }
                          board[i][j] = '.';
                      }
                  }
                  return false;//9个数都不能填满,返回false,循环终止，所以不用担心死循环
              }
          }
      }
      return true;//搜了一路放满了
  }

• 完整代码

  class Solution {
      public void solveSudoku(char[][] board) {
          backtrack(board);
      }
  
      //搜索树层用void,搜索树枝用booealn
      private boolean backtrack(char[][] board) {
          for (int i = 0; i < board.length; i++) {
              for (int j = 0; j < board[0].length; j++) {
                  if (board[i][j] == '.') {
                      for (char k = '1'; k <= '9'; k++) {
                          if (isValid(i, j, k, board)) {
                              board[i][j] = k;
                              boolean res = backtrack(board);
                              if (res) {//找到结果立刻返回
                                  return true;
                              }
                              board[i][j] = '.';
                          }
                      }
                      return false;//9个数都不能填满，棋盘是演员
                  }
              }
          }
          return true;//搜了一路放满了
      }
  
      private boolean isValid(int row, int col, char k, char[][] board) {
          for (int i = 0; i < 9; i++) {
              if (board[row][i] == k) {
                  return false;
              }
          }
          for (int i = 0; i < 9; i++) {
              if (board[i][col] == k) {
                  return false;
              }
          }
  
          int startRow = row / 3 * 3;
          int startCol = col / 3 * 3;
          for (int i = startRow; i < startRow + 3; i++) {
              for (int j = startCol; j < startCol + 3; j++) {
                  if (board[i][j] == k) {
                      return false;
                  }
              }
          }
          return true;
      }
  }