回溯

EmiyaCC 于 2021-08-20 发布

回溯问题：是一种搜索方式，本质是穷举

可解决的问题：

  1. 组合问题：N 个数中按照一定规律找出 k 个数的集合（不强调元素排序）
  2. 切割问题：一个字符串按照一定规律有集中切割方式
  3. 子集问题：一个 N 个数的集合按照一定规律有多少符合条件的子集
  4. 排列问题：N 个数按照一定规律全排列，有几种排列方式（强调元素排序）
  5. 棋盘问题：N 皇后，解数独

https://github.com/youngyangyang04/leetcode-master

组合

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> tmpList = new ArrayList<>();
        helper(n, k, 1, tmpList);
        return list;
    }
    void helper(int n, int k, int startIdx, List<Integer> tmpList) {
        if (tmpList.size() == k) {
            list.add(new ArrayList<>(tmpList));
            return ;
        }
        for (int i = startIdx; i <= n; i ++) {
            tmpList.add(i);
            helper(n, k, i + 1, tmpList);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

// 剪枝版本，时间复杂度大大降低
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> tmpList = new ArrayList<>();
        helper(n, k, 1, tmpList);
        return list;
    }
    void helper(int n, int k, int startIdx, List<Integer> tmpList) {
        if (tmpList.size() == k) {
            list.add(new ArrayList<>(tmpList));
            return ;
        }
        // 剪枝，比如 n = 4, k = 3, 那么当第一个值为 3 时就没有意义再回溯了，因为长度不够了
        for (int i = startIdx; i <= n - (k - tmpList.size()) + 1; i ++) {
            tmpList.add(i);
            helper(n, k, i + 1, tmpList);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> tmpList = new ArrayList<>();
        helper(k, n, 1, tmpList, 0);
        return list;
    }
    void helper(int k, int n, int indexIdx, List<Integer> tmpList, int sum) {
        if (tmpList.size() == k) {
            if (sum == n) {
                list.add(new ArrayList<>(tmpList));
                return;
            }
        }
        for (int i = indexIdx; i <= 9; i ++) {
            // 比上题的组合多了一个检查 sum 的过程
            sum += i;
            tmpList.add(i);
            helper(k, n, i + 1, tmpList, sum);
            tmpList.remove(tmpList.size() - 1);
            sum -= i;
        }
    }
}

class Solution {
    List<String> list = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits == "" || digits.length() == 0) return list;
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        StringBuilder sb = new StringBuilder();
        helper(digits, numString, 0, sb);
        return list;
    }
    void helper(String digits, String[] numString, int len, StringBuilder sb) {
        if (len == digits.length()) {
            list.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(len) - '0'];
        for (int i = 0; i < str.length(); i ++) {
            sb.append(str.charAt(i));
            helper(digits, numString, len + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> tmpList = new ArrayList<>();
        helper(candidates, target, tmpList, 0, 0);
        return list;
    }
    void helper(int[] candidates, int target, List<Integer> tmpList, int sum, int startIdx) {
        if (sum == target) {
            list.add(new ArrayList<>(tmpList));
            return;
        } else if (sum > target) return;
        for (int i = startIdx; i < candidates.length; i ++) {
            tmpList.add(candidates[i]);
            sum += candidates[i];
            int tmpIdx = startIdx;
            helper(candidates, target, tmpList, sum, i);
            sum -= candidates[i];
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

// 剪枝版本
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> tmpList = new ArrayList<>();
        helper(candidates, target, tmpList, 0, 0);
        return list;
    }
    void helper(int[] candidates, int target, List<Integer> tmpList, int sum, int startIdx) {
        if (sum == target) {
            list.add(new ArrayList<>(tmpList));
            return;
        } else if (sum > target) return;
        for (int i = startIdx; i < candidates.length; i ++) {
            tmpList.add(candidates[i]);
            sum += candidates[i];
            // 判断 sum 是否大于 target，大于就不回溯了
            if (sum <= target) {
                int tmpIdx = startIdx;
                helper(candidates, target, tmpList, sum, i);
            }
            sum -= candidates[i];
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

// 剪枝版本
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> tmpList = new ArrayList<>();
        boolean[] vis = new boolean[candidates.length];
        helper(candidates, target, tmpList, 0, 0, vis);
        return list;
    }
    void helper(int[] candidates, int target, List<Integer> tmpList, int sum, int startIdx, boolean[] vis) {
        if (sum == target) {
            list.add(new ArrayList<>(tmpList));
            return;
        } else if (sum > target) return;
        for (int i = startIdx; i < candidates.length; i ++) {
            // + 跟上题的不同在于添加了一个 vis 数组记录访问过的位置，当前后两个位置的数相同且前面位置的数没有访问过，则后面位置的数不适用（保证不重复）
            if (i != 0 && candidates[i] == candidates[i - 1] && !vis[i - 1]) continue;
            vis[i] = true;
            tmpList.add(candidates[i]);
            sum += candidates[i];
            // 判断 sum 是否大于 target，大于就不回溯了
            if (sum <= target) {
                int tmpIdx = startIdx;
                // + 这里位置变成了 i + 1，因为每个数只能使用一次
                helper(candidates, target, tmpList, sum, i + 1, vis);
            }
            sum -= candidates[i];
            tmpList.remove(tmpList.size() - 1);
            vis[i] = false;
        }
    }
}

分割

class Solution {
    List<List<String>> list = new ArrayList<>();
    public List<List<String>> partition(String s) {
        List<String> tmpList = new ArrayList<>();
        helper(s, tmpList, 0);
        return list;
    }
    void helper(String s, List<String> tmpList, int startIdx) {
        if (startIdx >= s.length()) {
            list.add(new ArrayList<>(tmpList));
            return;
        }
        for (int i = startIdx; i < s.length(); i ++) {
            if (isPalindrome(s, startIdx, i)) {
                tmpList.add(s.substring(startIdx, i + 1));
                helper(s, tmpList, i + 1);
                tmpList.remove(tmpList.size() - 1);
            } else {
                continue;
            }
        }
    }
    //判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

// 本题的 return 条件是在小数点为 3 时判断是否合法，这就需要合法保存值之后还需要删除刚加上的字符串恢复成刚进函数体的样子，所以使用全局变量会方便很多
class Solution {
    List<String> list = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) return list;
        helper(s, 0, 0);
        return list;
    }
    StringBuilder sb = new StringBuilder();
    void helper(String s, int startIdx, int countPot) {
        if (countPot == 3) {
            if (isOk(s, startIdx, s.length() - 1)) {
                list.add(sb.append(s.substring(startIdx, s.length())).toString());
                for (int j = 0; j < s.length() - startIdx; j ++) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
            return;
        }
        for (int i = startIdx; i < s.length(); i ++) {
            if (isOk(s, startIdx, i)) {
                sb.append(s.substring(startIdx, i + 1));
                sb.append(".");
                helper(s, i + 1, countPot + 1);
                for (int j = 0; j < i - startIdx + 2; j ++) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            } else {
                break;
            }
        }
    }
    boolean isOk(String s, int startIdx, int endIdx) {
        if (endIdx < startIdx) return false;
        if (s.charAt(startIdx) == '0' && endIdx != startIdx) return false;
        int num = 0;
        for (int i = startIdx; i <= endIdx; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    } 
}

子集

// 无重复数字，子集 ii 的简化版
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> tmpList = new ArrayList<>();
        helper(nums, tmpList, 0);
        return list;
    }
    void helper(int[] nums, List<Integer> tmpList, int startIdx) {
        // 3. 添加需要新建一个 ArrayList 对象
        list.add(new ArrayList<>(tmpList));
        if (startIdx >= nums.length) return;
        for (int i = startIdx; i < nums.length; i ++) {
            tmpList.add(nums[i]);
            helper(nums, tmpList, i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

// 数组中有重复数字
// 该问题跟前面的组合问题一样，在遇到组合问题（数组中有重复数字），需要做的是，首先对数组进行排序，然后建立一个记录访问的数组，再逐步添加组合结果，注意添加时需要新建一个对象。
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 1. 排序
        Arrays.sort(nums);
        List<Integer> tmpList = new ArrayList<>();
        // 2. 设置 vis 数组记录是否访问过
        boolean[] vis = new boolean[nums.length];
        helper(nums, tmpList, 0, vis);
        return list;
    }
    void helper(int[] nums, List<Integer> tmpList, int startIdx, boolean[] vis) {
        // 3. 添加需要新建一个 ArrayList 对象
        list.add(new ArrayList<>(tmpList));
        if (startIdx >= nums.length) return;
        for (int i = startIdx; i < nums.length; i ++) {
            if (i != 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
            vis[i] = true;
            tmpList.add(nums[i]);
            helper(nums, tmpList, i + 1, vis);
            tmpList.remove(tmpList.size() - 1);
            vis[i] = false;
        }
    }
}

排列

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> tmpList = new ArrayList<>();
        // 1. 使用 vis 数组记录元素的出现情况
        boolean[] vis = new boolean[nums.length];
        helper(nums, tmpList, vis);
        return list;
    }
    void helper(int[] nums, List<Integer> tmpList, boolean[] vis) {
        if (tmpList.size() == nums.length) {
            list.add(new ArrayList<>(tmpList));
            return;
        }
        for (int i = 0; i < nums.length; i ++) {
            // 2. 如果元素之前出现过就不再使用
            if (vis[i]) continue;
            vis[i] = true;
            tmpList.add(nums[i]);
            helper(nums, tmpList, vis);
            tmpList.remove(tmpList.size() - 1);
            vis[i] = false;
        }
    }
}

// 含重复数字，处理跟上面一样
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 1. 先排序，为处理重复的数字做准备
        Arrays.sort(nums);
        boolean[] vis = new boolean[nums.length];
        List<Integer> tmpList = new ArrayList<>();
        helper(nums, tmpList, vis);
        return list;
    }
    void helper(int[] nums, List<Integer> tmpList, boolean[] vis) {
        if (tmpList.size() == nums.length) {
            list.add(new ArrayList<>(tmpList));
            return;
        }
        for (int i = 0; i < nums.length; i ++) {
            if (vis[i]) continue;
            // 2. 如果两个元素相同，前一个元素没用到，那么后一个元素也不用，防止重复，跟前面一样
            if (i != 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
            tmpList.add(nums[i]);
            vis[i] = true;
            helper(nums, tmpList, vis);
            vis[i] = false;
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

class Solution {
    List<String> list = new ArrayList<>();
    public String[] permutation(String s) {
        StringBuilder sb = new StringBuilder();
        char[] strs = s.toCharArray();
        // 对应字符串数组需要先进行排序，为后面不重复出现相同结果做铺垫
        Arrays.sort(strs);
        boolean[] vis = new boolean[strs.length];
        helper(strs, sb, vis);
        // 输出格式，注意下
        return list.toArray(new String[list.size()]);
    }
    void helper(char[] strs, StringBuilder sb, boolean[] vis) {
        if (sb.length() == strs.length) {
            list.add(sb.toString());
            return;
        }
        for (int i = 0; i < strs.length; i ++) {
            if (vis[i]) continue;
            // 对于类似 aabc 这种的，这里是防止出现同一种结果的出现，需要前面先排序才可以这样写
            if (i != 0 && strs[i] == strs[i - 1] && !vis[i - 1]) continue;
            vis[i] = true;
            sb.append(strs[i]);
            helper(strs, sb, vis);
            sb.deleteCharAt(sb.length() - 1);
            vis[i] = false;
        }
    }
}

棋盘问题

// 思路：给定 n * n 的矩阵，那么从一层一层的放棋子，放下一层棋子时判断是否可以放棋子，结束条件是可以放棋子的层数达到 n，即已经在 n 层中都放了棋子
class Solution {
    List<List<String>> list = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        helper(n, 0, chessboard);
        return list;
    }
    void helper(int n, int row, char[][] chessboard) {
        if (row == n) {
            list.add(Array2List(chessboard));
            return;
        }
        for (int col = 0; col < n; col ++) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                helper(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
    boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i = 0; i < n; i ++) {
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查45度对角线
        for (int i= row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

// N 皇后问题是一行一行的放棋子，数独问题有初始的数，所有需要整体的判断，两个 for 循环依次填满整个矩阵
// 判断是否合适依据：1. 行唯一； 2. 列唯一； 3. 小区域唯一
class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }

    private boolean solveSudokuHelper(char[][] board){
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++){ // 遍历行
            for (int j = 0; j < 9; j++){ // 遍历列
                if (board[i][j] != '.'){ // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)){
                        board[i][j] = k;
                        if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        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] == val){
                    return false;
                }
            }
        }
        return true;
    }
}

其他

// 不能排序，所以前面的排序后判断连续两个数字的方法不行了，换一个方法，每个循环都设置一个 vis 数组，记录本次递归加入的数字是否不同
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<Integer> tmpList = new ArrayList<>();
        helper(nums, tmpList, 0);
        return list;
    }
    void helper(int[] nums, List<Integer> tmpList, int startIdx) {
        if (tmpList.size() >= 2) list.add(new ArrayList<>(tmpList));
        // 记录本次加入的数字是什么
        boolean[] vis = new boolean[201];
        for (int i = startIdx; i < nums.length; i ++) {
            // tmpList 不为空且 tmpList 的最后一个值比要加入的值大则不加入
            // 当加入的数是之前已经加入过了，则不加入
            if ((!tmpList.isEmpty() && nums[i] < tmpList.get(tmpList.size() - 1)) || (vis[nums[i] + 100])) continue;
            vis[nums[i] + 100] = true;
            tmpList.add(nums[i]);
            helper(nums, tmpList, i + 1);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

// 定义一个 Map<String, Map<String, Integer>> map 来记录一个节点的可到达节点及其次数
// 结束条件是：可到达的点个数是 票数 + 1
// 使用 Deque 来记录是为了获得 Stack 的先进后出的特性，同时是 LinkedList 结构，方便之后转换成 ArrayList
class Solution {
    Map<String, Map<String, Integer>> map = new HashMap<>();
    Deque<String> res = new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        // 1. 完成整个 map 图
        for (List<String> t : tickets) {
            Map<String, Integer> temp = new HashMap<>();
            if(map.containsKey(t.get(0))){
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            }else{
                // 2. 升序Map，关键步骤，省的排序了，不然还要对 temp l
                temp = new TreeMap<>();
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);
        }
        // 3. 添加头节点
        res.add("JFK");
        helper(tickets.size());
        return new ArrayList<>(res);
    }
    boolean helper(int ticketNum){
        // 4. 推出条件
        if(res.size() == ticketNum + 1){
            return true;
        }
        // 5. 获取本次递归的前节点
        String last = res.getLast();
        if(map.containsKey(last)){//防止出现null
            // 6. 循环遍历所有可能的值
            for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
                int count = target.getValue();
                if(count > 0){
                    res.add(target.getKey());
                    target.setValue(count - 1);
                    // 7. 剪枝，当找到了就退出
                    if(helper(ticketNum)) return true;
                    res.removeLast();
                    target.setValue(count);
                }
            }
        }
        return false;
    }
}