代码随想录_回溯

回溯

77.组合

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路: 回溯

优化: 剪枝

注意代码中i，就是for循环里选择的起始位置。

for (int i = startIndex; i <= n; i++) 

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

组合位数够多的可以截断, 不再进行递归, 组合位数不足的直接剪枝

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();// 存储结果
    List<Integer> path = new ArrayList<>();// 存储每一次的合法值

    public List<List<Integer>> combine(int n, int k) {
        backtracing(n,k,1);
        return res;
    }
    // n: 可用数字总个数,k: 需要的组合位数,start: 当前开始for循环处理的数值
    public void backtracing(int n,int k,int start) {
        // 1. 递归终止条件
        if(path.size() == k) {// 收集位数足够, 返回
            res.add(new ArrayList<>(path));
            return;
        }
        // 2. 单层递归逻辑
        // 					剪枝
        for(int i = start;i <= n - (k - path.size()) + 1;i++) {
            path.add(i);// 添加该位
            backtracing(n,k,i+1);// 添加下一位
            path.removeLast();// 移除该位
        }
    }
}

216.组合总和 III

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

思路: 回溯, 计算sum

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    //                                      目标位数, 目标和 
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracing(k,n,1,0);
        return res;
    }

    public void backtracing(int k,int targetSum,int start,int sum) {
        // 1. 递归终止条件: 当前sum > targetSum || size大小为目标值, 无需向下递归
        if(sum > targetSum) return;
        if(path.size() == k) {
            if(sum == targetSum) res.add(new ArrayList<>(path));
            return;
        }
        // 2. 单层递归逻辑
        for(int i = start;i <= 9 - (k - path.size()) + 1;i++) {
            sum+=i;
            path.add(i);

            backtracing(k,targetSum,i+1,sum);
            
            sum-=i;
            path.removeLast();
        }
    }
}

17.电话号码的字母组合

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

思路: 回溯, 定义一个StringBuilder记录path, 定义一个下标记录当前for循环遍历的数字对应的字符串

多个集合求组合, 每层遍历都从index = 0开始

代码:

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

    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0) return res;

        String[] str = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        backtracing(digits,str,0);
        return res;
    }
    // 记录path
    StringBuilder sb = new StringBuilder();            // start控制数字
    public void backtracing(String digits,String[] str,int start) {
        if(start == digits.length()) {// 此时start走到边界, 没有对应的数字
            res.add(sb.toString());
            return;
        }
        // 找到该数字对应的字符串
        String s = str[digits.charAt(start) - '0'];
        // 遍历字符串, 根据数字字符串进行递归和回溯
        for(int i = 0;i < s.length();i++) {// 每个字符串都是从index==0开始遍历
            sb.append(s.charAt(i));
            backtracing(digits,str,start+1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

}

39.组合总和

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

思路: 回溯, 注意剪枝, 下一层遍历起始位置是当层起始位置(同一个元素可被重复选取)

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 对原数组排序, 数字递增便于剪枝
        Arrays.sort(candidates);
        backtracing(candidates,new ArrayList(),target,0,0);
        return res;
    }
    //                                                               start: 数字起始遍历下标
    public void backtracing(int[] nums,List<Integer> path,int target,int sum,int start) {
        if(sum == target) {
            res.add(new ArrayList(path));// !!new
            return;
        }
        //                                   剪枝
        for(int i = start;i < nums.length && sum + nums[i] <= target;i++) {
            path.add(nums[i]);
            sum+=nums[i];
            backtracing(nums,path,target,sum,i);// 可重复, 从i开始
            path.remove(path.size() - 1);
            sum-=nums[i];
        }
    }
}

40.组合总和 II

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合

思路: 建立一个标记数组记录该数字有没有被使用过, 前后相等的数值, 前一个数值在遍历时就已经将同层上数值相等的后一个数可能的结果取遍.

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;// 标记nums[i]在该path中是否被使用过

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used,false);// 初始化, 没有
        Arrays.sort(candidates);// 排序, 以便剪枝

        backtracing(candidates,new ArrayList(),target,0,0);
        return res;
    }

    public void backtracing(int[] nums,List<Integer> path,int target,int sum,int start) {
        if(target == sum) {
            res.add(new ArrayList(path));
            return;
        }

        for(int i = start;i < nums.length && sum + nums[i] <= target;i++) {
            // 树层去重: 前一个没有被使用过, 后一个与前一个相同
            if(i > 0 && nums[i] == nums[i - 1] && used[i-1] == false) continue;

            path.add(nums[i]);
            sum+=nums[i];
            used[i] = true;

            backtracing(nums,path,target,sum,i+1);

            path.remove(path.size() - 1);
            sum-=nums[i];
            used[i] = false;
        }
    }
}

131.分割回文串

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是

回文串。返回 s 所有可能的分割方案。

思路: 分割位置start就代表: 该位置及之前的字符 是被分割出来的一串子字符串

代码:

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

    public List<List<String>> partition(String s) {
        backtracing(s,0,new StringBuilder());
        return res;
    }

    public void backtracing(String s,int start,StringBuilder sb) {
        // 1. 分割位置到了末尾, 结束
        if(start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 2. 循环回溯
        for(int i = start;i < s.length();i++) {
            sb.append(s.charAt(i));// 每轮会有新的sb进行分割
            if(isOK(sb)) {
                path.add(sb.toString());
                backtracing(s,i+1,new StringBuilder());
                path.remove(path.size() - 1);
            }
        }
    }

    // 判断是否是回文串
    public boolean isOK(StringBuilder sb) {
        for(int i = 0;i < sb.length()/2;i++) {
            if(sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) return false;
        }
        return true;
    }
}

93.复原 IP 地址

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

思路: 回溯, 根据 子串是否合法 和 dotCount大小剪枝

代码:

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

    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backtracing(sb,0,0);
        return res;
    }

    public void backtracing(StringBuilder sb,int dotCount,int start) {
        if(dotCount == 3) {// 验证第四段数字
            if(isValid(sb,start,sb.length() - 1)) {
                res.add(sb.toString());
            }
            return;// 记的return
        }

        for(int i = start;i < sb.length();i++) {
            if(isValid(sb,start,i)) {
                sb.insert(i+1,'.');
                dotCount+=1;
                backtracing(sb,dotCount,i+2);
                sb.deleteCharAt(i+1);
                dotCount-=1;
            }else break;// 注意, 该子串不合法以后就要break, 避免继续循环查询不合法的子串
        }
    }

    public boolean isValid(StringBuilder sb,int start,int end) {
        if(start > end) {// 下标不对, 不合法
            return false;
        }else if(sb.charAt(start) == '0' && start != end) {// ... .0 不合法
            return false;
        }else {// 数值总和超过255, 不合法
            int num = 0;
            for(int i = start;i <= end;i++) {
                num = num * 10 + sb.charAt(i) - '0';
                if(num > 255) return false;
            }
        }

        return true;
    }
}

78.子集

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

思路: 每层递归都要收集path(每一种组合情况都是一个子集)

注: 子集问题可以不写每层递归退出条件, 因为退出条件是根据数组下标, 而数组下标的合法性在for里也会进行判断, 若不合法直接结束.

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList();
    List<Integer> path = new ArrayList();

    public List<List<Integer>> subsets(int[] nums) {
        backtracing(nums,0);
        return res;
    }

    public void backtracing(int[] nums,int start) {
        res.add(new ArrayList(path));// 放在这个位置可以收集到{},刚好收集完整
        if(start == nums.length) return;

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

90.子集 II

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

思路: 树层去重, 树枝剪枝, 每层收集

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);// 注意, 为了成功去重, 一定要排序
        backtracing(nums,0);
        return res;
    }

    public void backtracing(int[] nums,int start) {
        res.add(new ArrayList<>(path));// 每个子集都要收集
        if(start == nums.length) return;

        for(int i = start;i < nums.length;i++) {
            if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            // 前后两位值相等 && 前一位没有被使用过
            path.add(nums[i]);
            used[i] = true;
            backtracing(nums,i+1);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

491.非递减子序列

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况.

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

思路: 哈希表记录数字是否使用过

不能重排序使用used, 因为要保持原来的顺序进行比较去重, 如2 7 6 7 如果排序:2 6 7 7 会被收集, 若不排序则不会被收集

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracing(nums,0);
        return res;
    }

    public void backtracing(int[] nums,int start) {
        if(path.size() > 1) res.add(new ArrayList<>(path));
        if(start == nums.length) return; 

        int[] used = new int[201];

        for(int i = start;i < nums.length;i++) {
            if(!path.isEmpty() && nums[i] < path.get(path.size() - 1) || used[nums[i] + 100] == 1) continue;
            // 当前要加入的数值小于path前一个数值 || 当前数值已经被使用过 : 跳过
            path.add(nums[i]);
            used[nums[i]+100] = 1;// 不需要回溯, 因为used每一层都会重建, 只会在当层去重
            backtracing(nums,i+1);
            path.remove(path.size() - 1);
        }
    }
}

46.全排列

46. 全排列

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

思路:

1. 使用used数组记录哪些数字被使用过, 哪些没有被使用过, 从而不重复选取元素
2. 每次for从0开始

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtracing(nums);
        return res;
    }

    public void backtracing(int[] nums) {
        if(path.size() == nums.length) {
            res.add(new ArrayList<>(path));
        }

        for(int i = 0;i < nums.length;i++) {
            if(used[i]) continue;// 树枝中不需要再取已经取过的数
            
            path.add(nums[i]);
            used[i] = true;
            backtracing(nums);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

47.全排列 II

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

思路: 由于包含重复数字, 需要进行去重(used + sort)

代码:

java">class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);// 易错, 为了去重
        backtracing(nums);
        return res;
    }

    public void backtracing(int[] nums) {
        if(path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0;i < nums.length;i++) {
            // 树层去重
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;// used[i-1]易错
            if(used[i]) continue;// 树枝中不需要再取已经取过的数

            path.add(nums[i]);
            used[i] = true;
            backtracing(nums);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

51.N 皇后

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路: 二维数组的回溯, 对棋盘逐行递归

代码:

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

    public List<List<String>> solveNQueens(int n) {
        // 1. 初始化棋盘
        // 1.1 创建空棋盘
        char[][] chessboard = new char[n][n];
        // 1.2 填充空棋盘
        for(char[] c : chessboard) {
            Arrays.fill(c,'.');
        }
        // 2. 回溯
        backtracing(n,0,chessboard);
        // 3. 返回
        return res;
    }

    public void backtracing(int n,int row,char[][] chessboard) {
        // 1. 递归出口: 棋盘走完最后一行
        if(row == n) {
            res.add(arrayToList(chessboard));// 存入合法的棋盘
            return;
        }
        // 2. 单层逻辑: 放置Q
        for(int col = 0;col < n;col++) {// 每层for处理同一行不同列
            if(isValied(row,col,n,chessboard)) {// 当前位置合法, 放入
                chessboard[row][col] = 'Q';
                backtracing(n,row + 1,chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    // 判断当前位置是否合法
    // 由于每层for只会在同层选一个位置放置, 然后就向下一列递归, 因此不需要检查同行
    // 当走到当前row的时候, row及row之前已经被填充过, 之后为空, 因此只需要检查row之前
    public boolean isValied(int row,int col,int n,char[][] chessboard) {
        // 1. 判断同列
        for(int i = 0;i < row;i++) {
            if(chessboard[i][col] == 'Q') return false;
        }
        // 2. 判断45°角
        for(int i = row - 1,j = col - 1;i >= 0 && j >= 0;i--,j--) {
            if(chessboard[i][j] == 'Q') return false;
        }
        // 3. 判断135°角
        for(int i = row - 1,j = col + 1;i >= 0 && j < n;i--,j++) {
            if(chessboard[i][j] == 'Q') return false;
        }
        // 4. 合法
        return true;
    }
    // 记录整个棋盘的布局: 将棋盘的每一行转为一个String, 所有行存入list
    public List<String> arrayToList(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for(char[] c : chessboard) {// 处理每一行, 变为String
            list.add(String.copyValueOf(c));// 存入每一行到list
        }
        return list;
    }
}

37.解数独

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

思路:

回溯三部曲:

1. 递归函数以及参数: boolean backtracing(char[][] board), boolean: 解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用boolean返回值。
2. 递归终止条件: 本题递归不用终止条件，递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了）
3. 单层搜索逻辑: 需要的是一个二维的递归 （一行一列）一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性

代码:

java">class Solution {
    public void solveSudoku(char[][] board) {
        backtracing(board);
    }

    // 整个棋盘遍历完, 递归结束, 结束条件在for里, 不用在外面再判断
    public boolean backtracing(char[][] board) {
        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++) {
                    if(isValid(i,j,k,board)) {
                        board[i][j] = k;
                        if(backtracing(board)) return true;// 递归向上层返回
                        board[i][j] = '.';
                    }
                }
                // 该位置9个数字都不合法, 该种情况不正确, return false
                return false;
            }
        }
        // 最底层的return true: 整个棋盘遍历完, 没有返回false, 说明找到了合法的情况, return true
        return true;
    }

    public boolean isValid(int row,int col,char k,char[][] board) {
        // 扫描行
        for(int j = 0;j < 9;j++) {
            if(board[row][j] == 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;
    }
}