回溯算法

hiriki2023-01-102023-01-10

组合

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

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

示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

思路草稿

题解

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return result;
    }

    private void backTracking(int n,int k,int start){
        if(path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }

        for(int i = start;i<=n-(k-path.size())+1;i++){ // 剪枝
        // for(int i = start;i<=n;i++){
            path.add(i);
            backTracking(n,k,i+1);
            path.remove(path.size()-1); // 回溯，移除最后一个元素
        }
    }
}

组合总和III

leetcode题目链接

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

思路草稿

组合总和III

题解

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

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k,n,0,1);
        return res;
    }

    private void backTracking(int k,int n,int sum,int start){
        if(path.size()==k){ // 终止条件
            if(sum==n){
                res.add(new ArrayList<>(path));
            }
            return;
        }

        if(sum>n){ // 剪枝
            return;
        }

        for(int i = start;i<=9-(k-path.size())+1;i++){ // 剪枝
            path.add(i);
            sum+=i;
            backTracking(k,n,sum,i+1);
            path.remove(path.size()-1);
            sum-=i;
        }
    }
}

电话号码的字母组合

leetcode题目链接

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

思路草稿

电话号码的字母组合

题解

class Solution {
    StringBuilder sb = new StringBuilder();
    List<String> res = new ArrayList<>();
    String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    public List<String> letterCombinations(String digits) {
        if(digits==""||digits.length()==0){
            return res;
        }
        backTracking(digits,0);
        return res;
    }

    private void backTracking(String digits,int index){
        if(index==digits.length()){
            res.add(sb.toString());
            return;
        }

        String temp = map[digits.charAt(index)-'0'];
        for(int i = 0;i<temp.length();i++){
            sb.append(temp.charAt(i));
            backTracking(digits,index+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

组合总和

leetcode题目链接

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

思路草稿

组合总和

题解

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

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates,0,target,0);
        return res;
    }

    private void backTracking(int[] candidates,int sum,int target,int start){

        if(sum>target){
            return;
        }

        if(sum==target){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = start;i<candidates.length;i++){
            if(sum+candidates[i]>target){  // 剪枝，排序后如果有一个组合和大雨target，后面的组合也都大于target，没有必要遍历，直接退出
                break;
            }
            path.add(candidates[i]);
            sum+=candidates[i];
            backTracking(candidates,sum,target,i);
            path.remove(path.size()-1);
            sum-=candidates[i];
        }
    }
}

组合总和II

leetcode题目链接

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

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

说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

思路草稿

组合总和II

题解

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used; // 记录元素是否遍历过

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used,false);
        Arrays.sort(candidates); // 将重复值放在一起，排序，剪枝以及去重
        backTracking(candidates,target,0,0);
        return res;
    }

    private void backTracking(int[] candidates,int target,int sum,int start){
        if(sum>target){ 
            return;
        }

        if(sum==target){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = start;i<candidates.length;i++){
            if(sum+candidates[i]>target){ // 剪枝
                break;
            }

            // 同一树层出现重复元素，used[i-1]=false 表示在同一层
            if(i>0&&candidates[i]==candidates[i-1]&&!used[i-1]){
                continue;
            }

            path.add(candidates[i]);
            sum+=candidates[i];
            used[i]=true;
            backTracking(candidates,target,sum,i+1);
            path.remove(path.size()-1);
            sum-=candidates[i];
            used[i]=false;
        }
    }
}

分割回文串

leetcode题目链接

给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

思路草稿

分割回文串

题解

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

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

    private void backTracking(String s,int start){
        if(start==s.length()){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = start;i<s.length();i++){
          // 回文串加入path
            if(isPalindrome(s,start,i)){
                path.add(s.substring(start,i+1));
            } else { // 否则i自增进入下一循环
                continue;
            }

            backTracking(s,i+1);
            path.remove(path.size()-1);
        }
    }

    private boolean isPalindrome(String s,int left,int right){
        for(;left<right;left++,right--){
            if(s.charAt(left)!=s.charAt(right)){
                return false;
            }
        }
        return true;
    }
}

复原IP地址

leetcode题目链接

有效 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 中的任何数字。可以按任何顺序返回答案。

思路草稿

复原IP地址

题解

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

    public List<String> restoreIpAddresses(String s) {
        backTracking(s,0,0);
        return res;
    }

    private void backTracking(String s,int start,int ip){

        // start等于s的长度并且ip段的数量是4，则加入结果集，并返回
        if(start==s.length()&&ip==4){
            res.add(sb.toString());
            return;
        }

        // 任意一个条件不满足直接返回
        if(start==s.length()||ip==4){
            return;
        }

        // 剪枝：ip段的长度最大是3，并且ip段处于[0,255]
        for(int i=start;i<s.length()&&i-start<3&&Integer.parseInt(s.substring(start,i+1))>=0&&Integer.parseInt(s.substring(start,i+1))<=255;i++){

            // 前导零直接break，因为后面所有子串也都是前导零
            if(i-start>=1&&s.charAt(start)=='0'){
                break;
            }

            // 加入分割后的子串
            sb.append(s.substring(start,i+1));
            // 网段数量小于3才加逗号，等于3则表示已经有三段，最后一段不加点
            if(ip<3){
                sb.append(".");
            }
            ip++;
            backTracking(s,i+1,ip);
            ip--;
            // 删除当前stringBuilder最后一个网段 左闭右开
            // start+ip 原子串起始位置加上点号数量
            // i+1+ip+1 原子串结束位置加上点号数量再往后加一位 
            sb.delete(start+ip,i+ip+2);
        }
    }
}

子集

leetcode题目链接

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

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

思路草稿

题解

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

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

    private void backTracking(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]);
            backTracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

子集II

leetcode题目链接

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

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

思路草稿

子集II

题解

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

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums,0);
        return res;
    }

    private void backTracking(int[] nums,int start){
        res.add(new ArrayList<>(path));
        
        if(start>=nums.length){
            return;
        }

        for(int i = start;i<nums.length;i++){
          // if(i>start&&nums[i]==nums[i-1]){  // 树层去重
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backTracking(nums,i+1);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }
}

递增子序列

leetcode题目链接

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

思路草稿

递增子序列

题解

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums,0);
        return res;
    }

    private void backTracking(int[] nums,int start){
        if(path.size()>1){
            res.add(new ArrayList<>(path));
        }

        if(start>=nums.length){
            return;
        }

        boolean[] used = new boolean[201]; // 每次递归都会重置used数组，即每个树层的used数组相互独立

        for(int i = start;i<nums.length;i++){
            if(!path.isEmpty()&&nums[i]<path.get(path.size()-1)||used[nums[i]+100]==true){  // 保证结果是递增的，并进行树层去重
                continue;
            }

            used[nums[i]+100]=true;
            path.add(nums[i]);
            backTracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

全排列

leetcode题目链接

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路草稿

全排列

题解

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

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

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

        for(int i = 0;i<nums.length;i++){
            if(used[i]==true){
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            backTracking(nums);
            path.remove(path.size()-1);
            used[i]=false;
        }
    }
}

全排列II

leetcode题目链接

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

思路草稿

全排列II

去重时：used[i-1]==true 为树枝去重，used[i-1]==false 为树层去重

题解

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

    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums==null||nums.length==0){
            return res;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backTracking(nums);
        return res;
    }

    private void backTracking(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;
            }
            if(used[i]==true){
                continue;
            }

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

重新安排行程

leetcode题目链接

给定一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请按字典排序返回最小的行程组合。

例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

思路草稿

重新安排行程

题解

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

    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));
        used = new boolean[tickets.size()];
        res.add("JFK");
        backTracking(tickets);
        return res;
    }

    private boolean backTracking(List<List<String>> tickets){
        if(res.size()==tickets.size()+1){
            return true;
        }

        for(int i = 0;i<tickets.size();i++){
            if(used[i]==true){
                continue;
            }

            if(tickets.get(i).get(0).equals(res.get(res.size()-1))){
                used[i]=true;
                res.add(tickets.get(i).get(1));

                if(backTracking(tickets)){
                    return true;
                }

                res.remove(res.size()-1);
                used[i]=false;
            }
        }

        return false;
    }
}

N皇后

leetcode题目链接

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

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

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

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

思路草稿

N皇后

题解

class Solution {

    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for(char[] c : chessboard){
            Arrays.fill(c,'.');
        }
        backTracking(chessboard,n,0);
        return res;
    }

    private void backTracking(char[][] chessboard,int n,int row){
        if(row==n){
            res.add(Array2List(chessboard));
            return;
        }

        for(int col = 0;col<n;col++){
            if(isVaild(chessboard,n,row,col)){
                chessboard[row][col]='Q';
                row++;
                backTracking(chessboard,n,row);
                row--;
                chessboard[row][col]='.';
            }
        }
    }

    private List Array2List(char[][] chessboard){
        List<String> list = new ArrayList<>();

        for(char[] c:chessboard){
            list.add(String.copyValueOf(c));
        }

        return list;
    }

    private boolean isVaild(char[][] chessboard,int n,int row,int col){
        // 列
        for(int i = 0;i<row;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;i--,j++){
            if(chessboard[i][j]=='Q'){
                return false;
            }
        }

        return true;
    }
}

解数独

leetcode题目链接

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

题解

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;
    }
}