回溯法典型题目总结

1. 求一个集合的全部子集。

思路：原集合中的每个元素有两种选择，要么加入要么不加入，所有元素的选择放在一起可构成了一系列等长向量，所有可能的等长向量构成了解空间。

import java.util.ArrayList;
import java.util.List;


public class Main{
    public static void main(String[] args){
        int[] nums = {1,2,3};
        Backtrace A = new Backtrace();
        List<List<Integer>> res = A.findAllSubSet(nums);
        System.out.println(res);
    }
}


class Backtrace{
    boolean[] isExist;
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findAllSubSet(int[] nums){
        isExist = new boolean[nums.length];
        backtrace(0, nums);
        return res;
    }
    public void backtrace(int index, int[] nums){
        if(index == nums.length){       //如果已经遍历一遍，那么就处理一下当前获得的解
            List<Integer> cur = new ArrayList<>();
            for(int i = 0; i < nums.length; i++){
                if(isExist[i] == true){
                    cur.add(nums[i]);
                }
            }
            res.add(new ArrayList<>(cur));
        }
        else{
            isExist[index] = false;
            backtrace(index + 1, nums);
            isExist[index] = true;
            backtrace(index + 1, nums);
        }
    }
}


/*
output:
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
*/

View Code

2. 求一个n元集合的k元子集（n>=k>0）

思路：和求n元集合的所有子集类似，用k来限制一下就可以了。

import java.util.ArrayList;
import java.util.List;

public class Main{
    public static void main(String[] args){
        int[] nums = {1,2,3,4,5};
        int k = 3;
        Backtrace A = new Backtrace();
        List<List<Integer>> res = A.findAllKSet(nums, k);
        System.out.println(res);
    }
}
class Backtrace{
    boolean[] isExist;
    List<List<Integer>> res = new ArrayList<>();
    int k;
    public List<List<Integer>> findAllKSet(int[] nums, int k){
        this.k = k;
        isExist = new boolean[nums.length];
        backtrace(0, nums);
        return res;
    }
    public void backtrace(int index, int[] nums){
        if(index == nums.length){       //如果已经遍历一遍，那么就处理一下当前获得的解
            List<Integer> cur = new ArrayList<>();
            int count = 0;
            for(int i = 0; i < nums.length; i++){
                if(isExist[i] == true){
                    cur.add(nums[i]);
                    count ++;
                }
            }
            if(count == k){
                res.add(new ArrayList<>(cur));
            }
            else{
                return ;
            }


        }
        else{
            isExist[index] = false;
            backtrace(index + 1, nums);
            isExist[index] = true;
            backtrace(index + 1, nums);
        }
    }
}


/*
output：
[[3, 4, 5], [2, 4, 5], [2, 3, 5], [2, 3, 4], [1, 4, 5], [1, 3, 5], [1, 3, 4], [1, 2, 5], [1, 2, 4], [1, 2, 3]]
*/

View Code

3. 不重复元素的全排列

思路：用used判断数组判断元素是否被使用，通过长度限制得到全排列。

import java.util.ArrayList;
import java.util.List;

public class Main{
    public static void main(String[] args){
        int[] nums = {1,2,3};
        BackTrace A = new BackTrace();
        List<List<Integer>> res = A.permutaion(nums);
        System.out.println(res);
    }
}

class BackTrace {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permutaion(int[] nums){
        if(0 == nums.length){
            return res;
        }
        used = new boolean[nums.length];
        backtrace(nums, 0, new ArrayList<Integer>());
        return res;
    }
    public void backtrace(int[] nums, int depth, List<Integer> cur){
        if(depth == nums.length){
            res.add(new ArrayList<>(cur));
            return ;
        }
        for(int i = 0; i < nums.length; i++){
            if(!used[i]){
                used[i] = true;
                cur.add(nums[i]);
                backtrace(nums, depth + 1, cur);
                cur.remove(cur.size() - 1);
                used[i] = false;
            }
        }
    }
}
/*
不重复元素，求所有全排列
output:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
*/

View Code

4. 重复元素的全排列

思路：在上一个题中，对重复的分支进行剪枝即可

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Main{
    public static void main(String[] args){
        int[] nums = {1,3,1};
        BackTrace A = new BackTrace();
        List<List<Integer>> res = A.permutaion(nums);
        System.out.println(res);
    }
}


class BackTrace {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permutaion(int[] nums){
        if(0 == nums.length){
            return res;
        }
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backtrace(nums, 0, new ArrayList<Integer>());
        return res;
    }
    public void backtrace(int[] nums, int depth, List<Integer> cur){
        if(depth == nums.length){
            res.add(new ArrayList<>(cur));
            return ;
        }
        for(int i = 0; i < nums.length; i++){
            if(!used[i]){
                //设前面的数为1，该数为1', 如果该数和前面的数是一样的，并且前面的数没有参与(言外之意上一次递归的时候已经参与完了)，按照这条路径下去(从1'开始)必然与前面的路径会相同（从1开始）
                //可以想想解空间树和递归的过程，详细的讲解看: https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
                if(i > 0 && nums[i] == nums[i-1] && !used[i-1]){
                    continue;
                }
                used[i] = true;
                cur.add(nums[i]);
                backtrace(nums, depth + 1, cur);
                cur.remove(cur.size() - 1);
                used[i] = false;
            }
        }
    }
}
/*
重复元素，求所有全排列
output:
[[1, 1, 3], [1, 3, 1], [3, 1, 1]]
*/

View Code

5. 电话号码对应字符串

思路：将这些字符和数字对应起来，然后简单回溯即可

import java.util.ArrayList;
import java.util.List;


public class Main{
    public static void main(String[] args){
        Solution A = new Solution();
        String digits = "25";
        List<String> res = A.letterCombinations(digits);
        System.out.println(res);
    }
}
class Solution {
    String[] tel = {
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
    };
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(0 == digits.length()){
            return res;
        }
        char[] number = digits.toCharArray();
        backtrace(number, 0, new StringBuilder());
        return res;
    }
    public void backtrace(char[] number, int index, StringBuilder cur){
        if(index == number.length){
            res.add(new String(cur));
            return ;
        }
        for(char c : tel[number[index] - '0'].toCharArray()){
            cur.append(c);
            backtrace(number, index + 1, cur);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}
/*
电话号码对应字符串
output:
[aj, ak, al, bj, bk, bl, cj, ck, cl]
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
*/

View Code

 6. 解数独

思路：在寻找一个解的时候，通过返回boolean可加快递归的返回。

题目链接：https://leetcode-cn.com/problems/sudoku-solver/

class Solution {
    boolean[][] colCheck = new boolean[9][10];
    boolean[][] rowCheck = new boolean[9][10];
    boolean[][][] blockCheck = new boolean[3][3][10];
    public void solveSudoku(char[][] board) {
        for(int row = 0; row < board.length; row++){
            for(int col = 0; col < board[0].length; col++){
                int num = board[row][col] - '0';
                if(1 <= num && num <= 9){
                    rowCheck[row][num] = true;
                    colCheck[col][num] = true;
                    blockCheck[row/3][col/3][num] = true;
                }
            }
        }
        backtrace(board, rowCheck, colCheck, blockCheck, 0, 0);
    }
    //回溯法寻找一个解的时候，可以通过返回boolean，用于加速递归的返回
    public boolean backtrace(char[][] board, boolean[][] rowCheck, boolean[][] colCheck,boolean[][][]blockCheck, int row, int col){
        if(col == board[0].length){
            col = 0;
            row++;
            if(row == board.length){
                return true;
            }
        }
        if(board[row][col] == '.'){
            for(int num = 1; num <= 9; num++){
                boolean canUse = !(rowCheck[row][num] || colCheck[col][num] || blockCheck[row/3][col/3][num]);
                if(canUse){
                    board[row][col] = (char)(num + '0');
                    rowCheck[row][num] = true;
                    colCheck[col][num] = true;
                    blockCheck[row/3][col/3][num] = true;

                    //这里返回的boolean加速了递归的返回，不用再向下执行了，而是直接返回了
                    //如果什么都不返回，上一步递归无法知道是否已经找到了可行解
                    if(backtrace(board, rowCheck, colCheck, blockCheck, row, col + 1)){
                        return true;
                    }

                    board[row][col] = '.';
                    rowCheck[row][num] = false;
                    colCheck[col][num] = false;
                    blockCheck[row/3][col/3][num] = false;
                }
            }
        }
        else{
            return backtrace(board, rowCheck, colCheck,blockCheck, row, col + 1);
        }
        return false;
    }
}

View Code

参考链接：

https://www.cnblogs.com/wuyuegb2312/p/3273337.html

https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/