1、剑指 Offer 34.二叉树中和为某一值

1.1 题目

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
image.png
image.png

1.2 思路

整体还是一个二叉树的先序遍历，需要注意以下两点：

  1. 判断trace是否添加到res的条件，不需要到root==null，只要root的左右子树都为null，且target已经减到零时就可以将trace添加到res了；
  2. 一定要注意：由于trace是一个引用，指向堆中唯一一块内存，递归中trace指向的也是同一个对象，因此当前节点add到trace，并递归了节点的左右子树之后，需要把节点从trace里remove掉，否则递归向上走到11时时，trace里还有之前的7。

不要忘了removeLast。

1.3 代码

  1. class Solution {
  2.     private List<List<Integer>> res = new ArrayList<>();
  4.     private LinkedList<Integer> trace = new LinkedList<>();
  6.     public List<List<Integer>> pathSum(TreeNode root, int target) {
  7.         if (root == null) {
  8.             return res;
  9.         }
  10.         dfs(root, target);
  11.         return res;
  12.     }
  14.     private void dfs(TreeNode root, int target) {
  15.         if (root == null) {
  16.             return;
  17.         }
  18.         trace.addLast(root.val);
  19.         target -= root.val;
  20.         if (root.left == null && root.right == null && target == 0) {
  21.             res.add(new ArrayList<>(trace));
  22.         }
  23.         dfs(root.left, target);
  24.         dfs(root.right, target);
  25.         trace.removeLast();
  26.     }
  27. }

2、剑指 Offer 38. 字符串的排列

2.1 题目

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：

输入：s = “abc” 输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

2.2 思路

这道题是回溯算法的经典题目。但需要注意以下几点：

  1. 字符串s里可能出现重复字母，比如aab，此时如果对结果不去重，会出现两个aab和两个baa，因为两个a是下标区分的，因此结果可以用set去重；

  2. 由于字符串每个下标上的字母只能使用一次，因此需要维护一个visited数组，当下标对应的字母add进sb时，则visited数组对应下标记为1，代表当前字符串对应下标的字母已经被使用了，在回退时也要将visited数组对应下标的值恢复为0。

    2.3 代码

    1. class Solution {
    2.  public String[] permutation(String s) {
    3.      Set<String> set = new HashSet<>();
    4.      StringBuilder sb = new StringBuilder();
    5.      int[] visited = new int[s.length()];
    6.      trace(s, set, sb, visited);
    7.      return set.toArray(new String[0]);
    8.  }
    10.  private void trace(String s, Set<String> set, StringBuilder sb, int[] visited) {
    11.      if (sb.toString().length() == s.length()) {
    12.          set.add(sb.toString());
    13.          return;
    14.      }
    15.      for (int i = 0; i < s.length(); ++i) {
    16.          if (visited[i] == 1) {
    17.              continue;
    18.          }
    19.          sb.append(s.charAt(i));
    20.          visited[i] = 1;
    21.          trace(s, set, sb, visited);
    23.          // 回退
    24.          sb.deleteCharAt(sb.toString().length() - 1);
    25.          visited[i] = 0;
    26.      }
    27.  }
    28. }

    3、剑指 Offer 12.矩阵中的路径

    好题。

    3.1 题目

    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
    例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）：
    image.png
    示例 1：

    输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true

示例 2：

输入：board = [[“a”,”b”],[“c”,”d”]], word = “abcd” 输出：false

3.2 思路

这道题是深度优先搜索和回溯思想的结合。

  1. 由于不能走已经走过的格子，因此需要维护一个二维数组visited，来记录哪些坐标已经走过了，dfs到上下左右的坐标时，需要判断当前的坐标是否已经走过，走过就不能再走了直接return；
  2. 注意dfs的起点，题中意思是路径的起始点可以是矩阵中的任意点，因此需要遍历这个二维数组，以数组中的任意一个点作为路径的起始点去dfs；

  3. 在dfs里需要注意回溯思想中的“添加”和“回退”。进入dfs后，开始下一轮dfs前，如果当前坐标对应的值可以添加到路径，则需要将当前坐标对应的visited二维数组中的点置为true，当前点的dfs退出前，需要将当前坐标对应的visited二维数组中的点置为false；

    3.3 代码

    1. class Solution {
    2.  private boolean[][] visited;
    3.  public boolean exist(char[][] board, String word) {
    4.      int h = board.length;
    5.      int w = board[0].length;
    6.      visited = new boolean[h][w];
    7.      for (int i = 0; i < h; ++i) {
    8.          for (int j = 0; j < w; ++j) {
    9.              if (dfs(i, j, 0, board, word)) {
    10.                  return true;
    11.              }
    12.          }
    13.      }
    14.      return false;
    15.  }
    17.  private boolean dfs(int i, int j, int index, char[][] board, String word) {
    18.      if (board[i][j] != word.charAt(index)) {
    19.          return false;
    20.      }
    21.      if (index == word.length() - 1) {
    22.          return true;
    23.      }
    25.      visited[i][j] = true;
    26.      int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    27.      for (int[] direction: directions) {
    28.          int ii = i + direction[0];
    29.          int jj = j + direction[1];
    30.          if (isValid(ii, jj, board) && !visited[ii][jj]) {
    31.              if (dfs(ii, jj, index + 1, board, word)) {
    32.                  return true;
    33.              }
    34.          }
    35.      }
    36.      visited[i][j] = false;
    37.      return false;
    38.  }
    40.  private boolean isValid(int i, int j, char[][] board) {
    41.      int h = board.length;
    42.      int w = board[0].length;
    43.      return i >= 0 && i < h && j >= 0 && j < w;
    44.  }
    45. }

    4、46. 全排列

    4.1 题目描述

    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1] 输出：[[1]]

4.2 思路

这道题是回溯算法经典的题目，由于非常典型可以说是回溯算法入门的第一道题目。

4.3 代码

  1. class Solution {
  2.     private List<List<Integer>> res = new LinkedList<List<Integer>>();
  4.     public List<List<Integer>> permute(int[] nums) {
  5.         LinkedList<Integer> trace = new LinkedList<Integer>();
  6.         traceBack(trace, nums);
  7.         return res;
  8.     }
  10.     void traceBack(LinkedList<Integer> trace, int[] nums) {
  11.         if (trace.size() == nums.length)
  12.         {
  13.             res.add(new LinkedList(trace));
  14.             return;
  15.         }
  17.         for (int num : nums)
  18.         {
  19.             if (trace.contains(num)) {
  20.                 continue;
  21.             }
  23.             trace.add(num);
  24.             traceBack(trace, nums);
  25.             trace.removeLast();
  26.         }
  27.     }
  28. }

5、78. 子集

5.1 题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0] 输出：[[],[0]]

5.2 思路

插入元素顺序：

  • 回溯算法顺序：[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3], []

  • 非回溯算法顺序：[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]

    5.3 代码

    回溯解法：

    1. class Solution {
    2.   private List<List<Integer>> res = new LinkedList<List<Integer>>();
    4.   public List<List<Integer>> subsets(int[] nums) {
    5.       LinkedList<Integer> trace = new LinkedList<Integer>();
    6.       int index = 0;
    7.       traceBack(trace, nums, index);
    8.       res.add(new LinkedList());
    9.       return res;
    10.   }
    12.   private void traceBack(LinkedList<Integer> trace, int[] nums, int index) {
    13.       if (trace.size() == nums.length || index == nums.length) {
    14.           return;
    15.       }
    17.       for (int i = index ; i < nums.length; ++i) {
    18.           trace.add(nums[i]);
    19.           res.add(new LinkedList(trace));
    20.           index = i + 1;
    21.           traceBack(trace, nums, index);
    22.           trace.removeLast();
    23.       }
    24.   }
    25. }

    思路清奇的非回溯解法：

    1. class Solution {
    2.   public List<List<Integer>> subsets(int[] nums) {
    3.       List<List<Integer>> res = new ArrayList<>();
    4.       res.add(new ArrayList<>());
    6.       for (int i = 0 ; i < nums.length; ++i) {
    7.           int size = res.size();
    8.           for (int j = 0 ; j < size; ++j) {
    9.               List<Integer> tmp = new ArrayList<>(res.get(j));
    10.               tmp.add(nums[i]);
    11.               res.add(tmp);
    12.           }
    13.       }
    15.       return res;
    16.   }
    17. }

    6、39. 组合总和

    6.1 题目描述

    给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
    说明：

  • 所有数字（包括 target）都是正整数；

  • 解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]

示例 2：

输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]

6.2 思路

还是一个经典的回溯题。需要注意的是：[2 ,2 ,3]和[2, 3, 2]只能出现[2, 2, 3]，因此回溯的函数里需要多一个for循环的起始index，将每次trace方法中的当前i的值指定给index，比如上面的例子，[2, 3]中一旦出现了3，就只能新增3之后的数字（包括当前的3），不能再添加前面的2了。

6.3 代码

  1. class Solution {
  2.     private List<List<Integer>> res = new LinkedList<>();
  3.     private int target;
  5.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  6.         if (candidates == null || candidates.length == 0) {
  7.             return res;
  8.         }
  9.         LinkedList<Integer> route = new LinkedList<>();
  10.         this.target = target;
  11.         trace(candidates, route, 0, 0);
  12.         return res;
  13.     }
  15.     private void trace(int[] candidates, LinkedList<Integer> route, int sum, int start) {
  16.         if (sum > target) {
  17.             return;
  18.         }
  19.         if (sum == target) {
  20.             res.add(new LinkedList<>(route));
  21.             return;
  22.         }
  24.         for (int i = start; i < candidates.length; ++i) {
  25.             route.addLast(candidates[i]);
  26.             sum += candidates[i];
  27.             trace(candidates, route, sum, i);
  28.             route.removeLast();
  29.             sum -= candidates[i];
  30.         }
  31.     }
  32. }

7、17. 电话号码的字母组合

7.1 题目

image.png

7.2 思路

回溯问题中加了点映射关系，整体思路还是回溯，需要注意：

  1. 相比传统的回溯，由于一个数字可以对应多个字符，因此回溯函数里需要双重循环；
  2. 由于数字2选取之后，只能从2之后的数字（不包含2）开始选取，因此需要维护一个index，每次新的trace方法遍历digists数组时，需要从这个index开始遍历；

  3. 注意这个index的维护，是i + 1, 而不是index + 1。

    7.3 代码

    1. class Solution {
    2.  private static Map<Character, List<Character>> map = new HashMap<>();
    3.  static {
    4.      map.put('2', Arrays.asList('a', 'b', 'c'));
    5.      map.put('3', Arrays.asList('d', 'e', 'f'));
    6.      map.put('4', Arrays.asList('g', 'h', 'i'));
    7.      map.put('5', Arrays.asList('j', 'k', 'l'));
    8.      map.put('6', Arrays.asList('m', 'n', 'o'));
    9.      map.put('7', Arrays.asList('p', 'q', 'r', 's'));
    10.      map.put('8', Arrays.asList('t', 'u', 'v'));
    11.      map.put('9', Arrays.asList('w', 'x', 'y', 'z'));
    12.  }
    13.  private List<String> res = new ArrayList<>();
    15.  public List<String> letterCombinations(String digits) {
    16.      if (digits == null || digits.length() == 0) {
    17.          return res;
    18.      }
    19.      dfs(digits, new StringBuilder(), 0);
    20.      return res;
    21.  }
    23.  private void dfs(String digits, StringBuilder trace, int index) {
    24.      if (trace.length() == digits.length()) {
    25.          res.add(trace.toString());
    26.          return;
    27.      }
    29.      for (int i = index; i < digits.length(); ++i) {
    30.          List<Character> values = map.get(digits.charAt(i));
    31.          for (int j = 0; j < values.size(); ++j) {
    32.              trace.append(values.get(j));
    33.              dfs(digits, trace, i + 1);
    34.              trace.deleteCharAt(trace.length() - 1);
    35.          }
    36.      }
    37.  }
    38. }

    8、494. 目标和

    8.1 题目

    给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
    示例 1：

    输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1 输出：1

8.2 思路

本题是一道回溯的题目。但是写法与传统的回溯有略微不一样，代码中不用回退（因为多加了一个sum变量的原因）。

8.3 代码

  1. class Solution {
  2.     private int cnt;
  3.     public int findTargetSumWays(int[] nums, int target) {
  4.         trace(nums, target, 0, 0);
  5.         return cnt;
  6.     }
  8.     private void trace(int[] nums, int target, int index, int sum) {
  9.         if (index == nums.length) {
  10.             if (sum == target) {
  11.                 ++cnt;
  12.             }
  13.         } else {
  14.             trace(nums, target, index + 1, sum + nums[index]);
  15.             trace(nums, target, index + 1, sum - nums[index]);
  16.         }
  17.     }
  18. }


参考

回溯算法套路详解