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/
来源: https://www.cnblogs.com/zhaijiayu/p/11566058.html