回溯

面试题08.12.八皇后（困难）

回溯算法

  1. class Solution {
  2.     private List<List<String>> result = new ArrayList<>();
  3.     public List<List<String>> solveNQueens(int n) {
  4.         char[][] nums = new char[n][n];
  5.         // 初始化
  6.         for(int i = 0; i < n; i++) {
  7.             nums[i] = new char[n];
  8.             for(int j = 0; j < n; j++) {
  9.                 nums[i][j] = '.';
  10.             }
  11.         }
  12.         backTrace(nums, 0);
  13.         return result;
  14.     }
  16.     private void backTrace(char[][] nums, int step) {
  17.         if(step == nums.length) {
  18.             List<String> snapshot = new ArrayList<>();
  19.             for(char[] num : nums) {
  20.                 snapshot.add(new String(num));
  21.             }
  22.             result.add(snapshot);
  23.         }
  24.         for(int i = 0; i < nums.length; i++) {
  25.             if(isOk(nums, step, i)) {
  26.                 nums[step][i] = 'Q';
  27.                 backTrace(nums, step + 1);
  28.                 nums[step][i] = '.';
  29.             }
  30.         }
  31.     }
  33.     private boolean isOk(char[][] nums, int step, int idx) {
  34.         int row = step;
  35.         int col = idx;
  37.         // 向上检测
  38.         while(row > 0) {
  39.             if(nums[--row][col] == 'Q') {
  40.                 return false;
  41.             }
  42.         }
  44.         row = step;
  45.         col = idx;
  46.         // 向左上角进行检测
  47.         while(row > 0 && col > 0) {
  48.             if(nums[--row][--col] == 'Q') {
  49.                 return false;
  50.             }
  51.         }
  53.         row = step;
  54.         col = idx;
  55.         // 向右上角进行检测
  56.         while(row > 0 && col < nums.length - 1) {
  57.             if(nums[--row][++col] == 'Q') {
  58.                 return false;
  59.             }
  60.         }
  61.         return true;
  62.     }
  63. }

37. 解数独

回溯

  1. class Solution {
  2.     // 记录每行 1~9 之间的某个数字是否出现过
  3.     private boolean[][] rows = new boolean[9][9];
  5.     // 记录每列 1~9 之间的某个数字是否出现过
  6.     private boolean[][] cols = new boolean[9][9];
  8.     // 记录每个 3*3 小宫格内 1~9 之间的某个数字是否出现过
  9.     private boolean[][][] block = new boolean[3][3][9];
  11.     // 记录空白格 “.” 的位置 
  12.     private List<int[]> space = new ArrayList<>();
  14.     private boolean isVaild = false;
  16.     public void solveSudoku(char[][] board) {
  17.         // 初始化 rows、cols、block 以及 space
  18.         for(int i = 0; i < 9; i++) {
  19.             for(int j = 0; j < 9; j++) {
  20.                 if(board[i][j] == '.') {
  21.                     space.add(new int[]{i, j});
  22.                 } else {
  23.                     int idx = board[i][j] - '0' - 1;
  24.                     rows[i][idx] = cols[j][idx] = block[i / 3][j / 3][idx] = true;
  25.                 }
  26.             }
  27.         }
  28.         backTrace(board, 0);
  29.     }
  31.     private void backTrace(char[][] board, int step) {
  32.         if(step == space.size()) {
  33.             isVaild = true;
  34.             return;
  35.         }
  36.         int[] pos = space.get(step);
  37.         int row = pos[0], col = pos[1];
  38.         // !isVaild 剪枝
  39.         for(int i = 0; i < 9 && !isVaild; i++) {
  40.             if(!rows[row][i] && !cols[col][i] && !block[row / 3][col / 3][i]) {
  41.                 rows[row][i] = cols[col][i] = block[row / 3][col / 3][i] = true;
  42.                 board[row][col] = (char)(i + '0' + 1);
  43.                 backTrace(board, step + 1);
  44.                 rows[row][i] = cols[col][i] = block[row / 3][col / 3][i] = false;
  45.             }
  46.         }
  47.     }
  48. }

17.电话号码的字母组合（中等）

  1. class Solution {
  2.     private List<String> result = new ArrayList<>();
  4.     Map<Character, String> phoneMap = new HashMap<Character, String>() {{
  5.             put('2', "abc");
  6.             put('3', "def");
  7.             put('4', "ghi");
  8.             put('5', "jkl");
  9.             put('6', "mno");
  10.             put('7', "pqrs");
  11.             put('8', "tuv");
  12.             put('9', "wxyz");
  13.         }};
  15.     public List<String> letterCombinations(String digits) {
  16.         if(digits == null || digits.length() == 0){
  17.             return result;
  18.         }
  19.         backTrace(digits, 0, new char[digits.length()]);
  20.         return result;
  21.     }
  23.     private void backTrace(String digits, int step, char[] path) {
  24.         if(step == digits.length()) {
  25.             result.add(new String(path));
  26.             return;
  27.         }
  28.         String opt = phoneMap.get(digits.charAt(step));
  29.         for(int i = 0; i < opt.length(); i++) {
  30.             path[step] = opt.charAt(i);
  31.             backTrace(digits, step + 1, path);
  32.         }
  33.     }
  34. }

77.组合（中等） 给n个数返回所有k个数的组合

回溯

  1. class Solution {
  2.     private List<List<Integer>> res = new ArrayList<>();
  4.     public List<List<Integer>> combine(int n, int k) {
  5.         backTrace(n, 1, k, new ArrayList<Integer>());
  6.         return res;
  7.     }
  9.     private void backTrace(int n, int step, int k, List<Integer> path) {
  10.         if(path.size() == k) {
  11.             res.add(new ArrayList<>(path));
  12.             return;
  13.         }
  15.         // 剪枝
  16.         if(step > n) {
  17.             return;
  18.         }
  20.         // 决策：不选
  21.         backTrace(n, step + 1, k, path);
  23.         // 决策：选
  24.         path.add(step);
  25.         backTrace(n, step + 1, k, path);
  26.         path.remove(path.size() - 1);
  27.     }
  28. }

回溯+剪枝优化

解题思路：
关键在于剪枝

  1. class Solution {
  3.     private List<List<Integer>> result = new ArrayList<>();
  5.     public List<List<Integer>> combine(int n, int k) {
  6.         backTrace(n, k, 1, new ArrayList<>());
  7.         return result;
  8.     }
  10.     private void backTrace(int n, int k, int cur, List<Integer> path) {
  11.         if(path.size() == k) {
  12.             result.add(new ArrayList<Integer>(path));
  13.             return;
  14.         }
  15.         // n - k + path.size() + 1 => 剪枝的关键
  16.         // 搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
  17.         // 搜索起点的上界 = n - (k - path.size()) + 1
  18.         for(int i = cur; i <= n - k + path.size() + 1; i++) {
  19.             path.add(i);
  20.             backTrace(n, k, i + 1, path);
  21.             path.remove(path.size() - 1);
  22.         }
  23.     }
  24. }

78.子集（中等） 所有的组合

解题思路：

  1. class Solution {
  2.     private List<List<Integer>> result = new ArrayList<>();
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         backTrace(nums, 0, new ArrayList<>());
  6.         return result;
  7.     }
  9.     private void backTrace(int[] nums, int stage, List<Integer> path) {
  10.         if(stage == nums.length) {
  11.             result.add(new ArrayList<>(path));
  12.             return;
  13.         }
  14.         // 决策：不选
  15.         backTrace(nums, stage + 1, path);
  17.         // 决策：选
  18.         path.add(nums[stage]);
  19.         backTrace(nums, stage + 1, path);
  20.         path.remove(path.size() - 1);
  21.     }
  22. }

90.子集II（中等）有重复数据

回溯

剪枝思路：

  1. 先对数值排序
  2. 考虑数组 [1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。也就是说，对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。

  3. 画决策树也能发现规律。

    1. class Solution {
    3.  private List<List<Integer>> result = new ArrayList<>();
    5.  public List<List<Integer>> subsetsWithDup(int[] nums) {
    6.      // 核心
    7.      Arrays.sort(nums);
    8.      backTrace(nums, 0, false, new ArrayList<Integer>());
    9.      return result;
    10.  }
    12.  private void backTrace(int[] nums, int k, boolean choose, List<Integer> path) {
    13.      if(k == nums.length) {
    14.          result.add(new ArrayList<>(path));
    15.          return;
    16.      }
    18.      backTrace(nums, k + 1, false, path);
    19.      // 剪枝，重复的要移除，画决策树，会发现，当做出不选择的决策后的路径，可能与上一阶段的路径相同，这时候得剪枝。
    20.      if(!choose && k > 0 && nums[k] == nums[k - 1]) {
    21.          return;
    22.      }
    23.      path.add(nums[k]);
    24.      backTrace(nums, k + 1, true, path);
    25.      path.remove(path.size() - 1);
    26.  }
    27. }

46.全排列（中等） 所有排列

回溯

  1. class Solution {
  2.     private List<List<Integer>> result = new ArrayList<>();
  4.     public List<List<Integer>> permute(int[] nums) {
  5.         backTrace(nums, 0, new ArrayList<Integer>());
  6.         return result;
  7.     }
  9.     private void backTrace(int[] nums, int k, List<Integer> path) {
  10.         if(k == nums.length) {
  11.             result.add(new ArrayList<>(path));
  12.             return;
  13.         }
  14.         for(int i : nums) {
  15.             if(path.contains(i)) {
  16.                 continue;
  17.             }
  18.             // 做选择
  19.             path.add(i);
  20.             // 递归
  21.             backTrace(nums, k + 1, path);
  22.             // 回溯，撤销选择
  23.             path.remove(path.size() - 1);
  24.         }
  25.     }
  26. }

47.全排列II（中等） 有重复数据

  1. class Solution {
  2.     private List<List<Integer>> result = new ArrayList<>();
  4.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  5.         // 核心
  6.         Arrays.sort(candidates);
  7.         backTrace(candidates, 0, target, new ArrayList<Integer>());
  8.         return result;
  9.     }
  11.     private void backTrace(int[] candidates, int k, int target, List<Integer> path) {
  12.         if(target == 0) {
  13.             result.add(new ArrayList<>(path));
  14.             return;
  15.         }
  17.         for(int i = k; i < candidates.length; i++) {
  18.             // 剪枝
  19.             if(target - candidates[i] < 0) {
  20.                 return;
  21.             }
  23.             // 剪枝
  24.             if(i > k && candidates[i] == candidates[i - 1]) {
  25.                 continue;
  26.             }
  27.             path.add(candidates[i]);
  28.             backTrace(candidates, i + 1, target - candidates[i], path);
  29.             path.remove(path.size() - 1);
  30.         }
  31.     }
  32. }

39.组合总和（中等） 选出某几个数相加为给定和，无重复数据，可以使用多次，不能有重复答案

排序+回溯

解题思路：

  1. 先将数组排序。

  2. 由于数组内元素可以重复使用，那么如果数组[1, 2, 3] 能满足题目，那么无论当前阶段选数组内哪个数，结果集都有可能重复，所以为了结果集不重复，可选列表的范围应为当前所选值到数组尾部。

    1. class Solution {
    2.  private List<List<Integer>> res = new ArrayList<>();
    4.  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    5.      // 排序是核心
    6.      Arrays.sort(candidates);
    7.      backTrace(candidates, 0, target, new ArrayList<Integer>());
    8.      return res;
    9.  }
    11.  private void backTrace(int[] candidates, int begin, int target, List<Integer> path) {
    12.      if(target == 0) {
    13.          res.add(new ArrayList<Integer>(path));
    14.      }
    15.      for(int i = begin; i < candidates.length; i++) {
    16.          int diff = target - candidates[i];
    17.          // 剪枝，当前差值小于0，后续直接剪枝，无需就相加
    18.          if(diff < 0){
    19.              return;
    20.          }
    21.          path.add(candidates[i]);
    22.          backTrace(candidates, i, diff, path);
    23.          path.remove(path.size() - 1);
    24.      }
    25.  }
    26. }

40.组合总和II（中等）选出某几个数相加为给定和，有重复数据，只能使用一次，不能有重复答案

  1. 先将数组排序
  2. 考虑数组 [1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。也就是说，对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。

  3. 由于数组内元素不可重复使用，那么无论当前阶段选数组内哪个数，结果集都有可能重复，所以为了结果集不重复，可选列表的范围应为当前所选值后一位到数组尾部。

    1. class Solution {
    2.  private List<List<Integer>> result = new ArrayList<>();
    4.  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    5.      Arrays.sort(candidates);
    6.      backTrace(candidates, 0, target, new ArrayList<Integer>());
    7.      return result;
    8.  }
    10.  private void backTrace(int[] candidates, int k, int target, List<Integer> path) {
    11.      if(target == 0) {
    12.          result.add(new ArrayList<>(path));
    13.          return;
    14.      }
    16.      for(int i = k; i < candidates.length; i++) {
    17.          // 剪枝
    18.          if(target - candidates[i] < 0) {
    19.              return;
    20.          }
    22.          // 剪枝
    23.          if(i > k && candidates[i] == candidates[i - 1]) {
    24.              continue;
    25.          }
    26.          path.add(candidates[i]);
    27.          backTrace(candidates, i + 1, target - candidates[i], path);
    28.          path.remove(path.size() - 1);
    29.      }
    30.  }
    31. }

216.组合总和III（中等） 选出k个数相加为给定和，没有重复数据，只能使用一次

  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  4.     public List<List<Integer>> combinationSum3(int k, int n) {
  5.         backTrace(k, n, 1, new ArrayList<Integer>());
  6.         return res;
  7.     }
  9.     private void backTrace(int k, int n, int stage, List<Integer> path) {
  10.         if(n == 0 && path.size() == k) {
  11.             res.add(new ArrayList<Integer>(path));
  12.             return;
  13.         }
  14.         if(path.size() == k || stage == 10) {
  15.             return;
  16.         }
  18.         // 不选
  19.         backTrace(k, n, stage + 1, path);
  20.         // 剪枝
  21.         if(n - stage < 0) {
  22.             return;
  23.         }
  24.         // 选
  25.         path.add(stage);
  26.         backTrace(k, n - stage, stage + 1, path);
  27.         path.remove(path.size() - 1);
  29.     }
  30. }

131.分割回文串（中等）

  1. class Solution {
  2.     List<List<String>> res = new ArrayList<>();
  4.     public List<List<String>> partition(String s) {
  5.         backTrace(s, s.length(), 0, new ArrayList<String>());
  6.         return res;
  7.     }
  9.     private void backTrace(String s, int len, int index, List<String> path) {
  10.         if(index == len) {
  11.             res.add(new ArrayList<>(path));
  12.             return;
  13.         }
  15.         for(int i = index; i < len; i++) {
  16.             String t = s.substring(index, i + 1);
  17.             if(!isPalindrome(t)){
  18.                 continue;
  19.             }
  20.             path.add(t);
  21.             backTrace(s, len, i + 1,  path);
  22.             path.remove(path.size() - 1);
  23.         }
  24.     }
  26.     private boolean isPalindrome(String s) {
  27.         if(s.length() == 0) {
  28.             return false;
  29.         }
  30.         int begin = 0, end = s.length() - 1;
  31.         while(begin <= end) {
  32.             if(s.charAt(begin) != s.charAt(end)) {
  33.                 return false;
  34.             }
  35.             begin++;
  36.             end--;
  37.         }
  38.         return true;
  39.     }
  40. }

93. 复原IP地址（中等）

  1. class Solution {
  2.     private List<String> res = new ArrayList<>();
  4.     public List<String> restoreIpAddresses(String s) {
  5.         backTrace(s, 0, 4, new ArrayList<String>());
  6.         return res;
  7.     }
  9.     private void backTrace(String s, int index, int step, List<String> path) {
  10.         if(step == 0 && index == s.length()) {
  11.             StringBuilder sb = new StringBuilder();
  12.             for(String num : path) {
  13.                 sb.append(num).append(".");
  14.             }
  15.             res.add(sb.toString().substring(0, sb.length() - 1));
  16.         }
  17.         // 剪枝
  18.         int len = s.length() - index;
  19.         if(len > step * 3 || len < step * 1) {
  20.             return;
  21.         }
  23.         for(int i = index; i < s.length() && i < index + 3; i++) {
  24.             String num = s.substring(index, i + 1);
  25.             // 剪枝
  26.             if(!isVaild(num)) {
  27.                 break;
  28.             }
  29.             path.add(num);
  30.             backTrace(s, i + 1, step - 1, path);
  31.             path.remove(path.size() - 1);
  32.         }
  33.     }
  35.     private boolean isVaild(String s) {
  36.         if(s.length() > 1 && s.charAt(0) == '0') {
  37.             return false;
  38.         }
  39.         int num = Integer.parseInt(s);
  40.         return num >= 0 && num <= 255;
  41.     }
  42. }

22.括号生成（中等）

回溯+栈

  1. class Solution {
  2.     List<String> res = new ArrayList<>();
  4.     private Stack<Character> stack = new Stack<>();
  6.     public List<String> generateParenthesis(int n) {
  7.         backTrace(n, n * 2, new ArrayList<Character>());
  8.         return res;
  9.     }
  11.     private void backTrace(int n, int step, List<Character> path) {
  12.         if(step == 0 && stack.isEmpty()) {
  13.             StringBuilder sb = new StringBuilder();
  14.             for(Character c : path) {
  15.                 sb.append(c + "");
  16.             }
  17.             res.add(sb.toString());
  18.             return;
  19.         }
  20.         if(step < 0) {
  21.             return;
  22.         }
  24.         path.add('(');
  25.         stack.push('(');
  26.         backTrace(n, step - 1, path);
  27.         path.remove(path.size() - 1);
  28.         stack.pop();
  30.         // 剪枝
  31.         if(stack.size() > n) {
  32.             return;
  33.         }
  35.         if(!stack.isEmpty() && stack.peek() == '(') {
  36.             stack.pop();
  37.             path.add(')');
  38.             backTrace(n, step - 1, path);
  39.             path.remove(path.size() - 1);
  40.             stack.push('(');
  41.         }
  42.     }
  43. }

回溯-优化

  1. class Solution {
  2.     List<String> res = new ArrayList<>();
  4.     public List<String> generateParenthesis(int n) {
  5.         backTrace(n, 0, 0, new StringBuilder());
  6.         return res;
  7.     }
  9.     private void backTrace(int max, int left, int right, StringBuilder cur) {
  10.         if(cur.length() == max * 2) {
  11.             res.add(cur.toString());
  12.             return;
  13.         }
  15.         if(left < max) {
  16.             cur.append("(");
  17.             backTrace(max, left + 1, right, cur);
  18.             cur.deleteCharAt(cur.length() - 1);
  19.         }
  21.         if(right < left) {
  22.             cur.append(")");
  23.             backTrace(max, left, right + 1, cur);
  24.             cur.deleteCharAt(cur.length() - 1);
  25.         }
  26.     }
  27. }