2024-06-04发表2024-06-04更新数据结构与算法31 分钟读完 (大约4684个字)

回溯法总结

回溯法其实就是递归，暴力搜索N叉树。做题画一颗N叉树，适当时剪枝。

回溯法能解决的问题：

组合问题：N个数里面按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

回溯法的基本模版

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

回溯法抽象为树形结构后，其遍历过程就是：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

组合问题

组合

https://leetcode.cn/problems/combinations/

class Solution {
    public List<List<Integer>> ans = new ArrayList<>();
    public Deque<Integer> path = new ArrayDeque<>();
    public void backTrait(int n, int start, int k){
        if(path.size()==k){
            ans.add(new ArrayList<>(path));//copy
            return;
        }
        for(int i=start; i<=n; ++i){
           path.add(i);
           backTrait(n, i+1, k);
           path.removeLast(); //回溯
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        backTrait(n, 1, k);
        return ans;
    }
}

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

解题思路：树形结构遍历、next greater去重

优化思路：如果剩下元素不足以凑齐K个，不用往下遍历。

// 如果path.size加上n-i+1还不够k，那么继续遍历下去也没用
// 符合i的条件为 path.size()+n-i+1 >= k
// namely i <= n-k+1-path.size()
for(int i=start; i<= n-k+1+path.size(); ++i){

组合2

https://leetcode.cn/problems/combination-sum-iii/

class Solution {
    public List<List<Integer>> ans = new ArrayList<>();
    public Deque<Integer> path = new ArrayDeque<>();
    public void backTrack(int k, int n, int start, int sum){
        if(path.size()==k && sum==n){
            ans.add(new ArrayList<>(path));
            return;
        }
        else if(path.size() > k) return;
        for(int i=start; i<=9; ++i){
            path.add(i);
            sum+=i;
            backTrack(k,n, i+1, sum);
            path.removeLast();
            sum-=i;
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTrack(k, n, 1, 0);
        return ans;
    }
}

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

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。与上题相比，就是加了一个和为k的限制。

电话号码的数字组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

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

难点在于集合的映射,本题每一个数字代表的是不同集合，也就是求不同集合之间的组合.

1 2	输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution {
    // 匿名内部类
    public Map<Character, String> map = new HashMap<>(){{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
    public List<String> ans = new ArrayList<>();
    public void backTrack(String digits, int index, StringBuilder path){
       if(path.length() == digits.length()){
           ans.add(path.toString());
           return;
       }
        char num = digits.charAt(index);
        String alphabet = map.get(num);
        for(int j=0; j<alphabet.length(); ++j){
            char letter = alphabet.charAt(j);
            path.append(letter);
            backTrack(digits, index+1, new StringBuilder(path));
            path.deleteCharAt(index);
        } 
    }
    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()) return ans;
        backTrack(digits, 0, new StringBuilder());
        StringBuilder sb = new StringBuilder();
        return ans;
    }
}

组合总和

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

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

https://leetcode.cn/problems/combination-sum/

1 2	输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]

vector<vector<int>> ret;
    vector<int> path;
    void backtrack(vector<int>& candidates, int target, int start){
        if(target<0) return;
        else if (target==0){
            ret.push_back(path);
            return;
        }
        for(int i=start; i<candidates.size(); ++i){
            int num = candidates[i];
            if(target-num<0) break; //剪枝优化
            path.push_back(num);
            backtrack(candidates, target-num, i); //注意这里是重复选取
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); //不排序会出问题！
        backtrack(candidates, target, 0);
        return ret;  
    }

本题与1.2组合2的区别在于，同一个数字可以无限制重复选取。故区别在递归时，startindex是从i开始（意味着本数字可以重复选取），而不是从i+1开始。

在求和问题中，排序之后加剪枝是常见的套路！

组合总和2

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

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

https://leetcode.cn/problems/combination-sum-ii/

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

vector<vector<int>> ret;
  vector<int> path;
  void backtrack(vector<int>& candidates, int target, int start, vector<int>& visited){
      if(target<0) return;
      else if (target==0){
          ret.push_back(path);
          return;
      }
      for(int i=start; i<candidates.size(); ++i){
          int num = candidates[i];
          if(target-num<0) break; //剪纸优化
        
          if(i>0 && candidates[i]==candidates[i-1] && visited[i-1]==0) 
            continue; //同一树层剪枝
          path.push_back(num);
          visited[i]= 1;
          backtrack(candidates, target-num, i+1, visited); 
          visited[i]= 0;
          path.pop_back();
      }
  }
  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
      vector<int> visited(candidates.size(), 0);
      sort(candidates.begin(), candidates.end()); //不排序会出问题！
      backtrack(candidates, target, 0, visited);
      return ret;  
  }

这道题与上一题的区别在于集合中元素是否重复，并且上一题中的元素可以重复选取，这题每个元素只能用一次。

要去重，否则1，2，2的组合会出现3次。去重是难点！

为了讲解这个去重问题，我自创了两个词汇，“树枝去重”和“树层去重”。

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上“使用过”，一个维度是同一树层上“使用过”。

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过

1 2	//TODO 另一种去重方式，不用used数组 if(i>start && candidates[i]==candidates[i-1])

对于组合问题，什么时候需要startIndex呢？

如果是一个集合来求组合的话，就需要startIndex，如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex.

切割

分割回文串

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

https://leetcode.cn/problems/palindrome-partitioning/

1 2	输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]

vector<vector<string>> ret;
    vector<string> path;
    bool is_hui(string& s, int l, int r){
        if(l>r) return false;
        while(l<r){
            if(s[l]!=s[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
    void backtrack(string& s, int start){
        if(start==s.size()){
            ret.push_back(path);
            return ;
        }
        for(int i=start; i<s.size();++i){
            if(is_hui(s, start, i)){
                path.push_back(s.substr(start, i-start+1));
            }
            else{
                continue;
            }
            backtrack(s, i+1); //i+1 
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backtrack(s, 0);
        return ret;
    }

回溯法怎么应用于切割问题？其实只要想象长度为n的串，分为若干段，每段长度可以相同，各段长度和为n。这不就是组合总和的思路嘛。candidate就是从1到n，target就是n，元素可以重复选取。

复原IP地址

https://leetcode.cn/problems/restore-ip-addresses/

子集问题

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

https://leetcode.cn/problems/subsets/

class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public void backTrack(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]);
            backTrack(nums, i+1);
            path.removeLast();
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        backTrack(nums, 0);
        return res;
    }
}

子集问题怎么解？在之前的问题中，我们都是收集叶子节点的结果。现在求子集，我们要收集每一个节点的结果！

收集结果的代码放在递归的第一行，收集本身。注意空子集在第一次调用时收集。

子集问题2

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

说明：解集不能包含重复的子集。

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

https://leetcode.cn/problems/subsets-ii/

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            // 而我们要对同一树层使用过的元素进行跳过
            if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex
                continue;
            }
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 去重需要排序
        backtracking(nums, 0);
        return result;
    }
};

这题与上题的区别在于集合可以包含重复元素，在选子集时会出现重复的情况，所以需要去重。

如何去重？树层去重（需要排序）。

递增子序列

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

1 2	- 输入: [4, 7, 6, 7] - 输出:[[4,7],[4,7,7],[4,6],[4,6,7],[7,7],[6,7]]

https://leetcode.cn/problems/non-decreasing-subsequences/

vector<vector<int>> ret;
  vector<int> path;
  void backtrack(vector<int>& nums, int start){
    	//提前收集
      if(path.size()>=2) 
          ret.push_back(path);
      //判断返回的方式
      if(start>=nums.size()) return;
      
      unordered_set<int> uset;
      for(int i=start; i<nums.size();++i){    
          if((!path.empty() && nums[i]<path.back())
              ||uset.find(nums[i])!=uset.end())  //之前的数字出现过了！
              continue; 
          uset.insert(nums[i]); //插入元素
          path.push_back(nums[i]);  
          backtrack(nums, i+1);
          path.pop_back();
          
      }
  }
  vector<vector<int>> findSubsequences(vector<int>& nums) {
      backtrack(nums, 0);
      return ret;
  }

这道题类似子集问题2，只不过要求找到的子集长度至少为2，并且递增。

本题不能使用之前的去重逻辑！求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。

所以需要利用set去重。

这也是需要注意的点，unordered_set<int> uset; 是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！

排列

全排列问题

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

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

https://leetcode.cn/problems/permutations/

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue; // path里已经收录的元素，直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

想象一颗N叉树，不能重复选取元素，startindex也没用了，统一从0开始，借助used数组。

大家此时可以感受出排列问题的不同：

每层都是从0开始搜索而不是startIndex
需要used数组记录path里都放了哪些元素了

全排列问题2

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

1 2	- 输入：nums = [1,1,2] - 输出： [[1,1,2], [1,2,1], [2,1,1]]

https://leetcode.cn/problems/permutations-ii/

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            if (used[i] == false) {
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

这题需要去重了，否则长度为3的数组全排列应该有3x2x1=6个。

如何去重？sort后再树层去重？

中途休息

性能分析

之前并没有分析各个问题的时间复杂度和空间复杂度，这次来说一说。

子集问题分析：

时间复杂度：$O(n × 2^n)$，因为每一个元素的状态无外乎取与不取，所以时间复杂度为$O(2^n)$，构造每一组子集都需要填进数组，又有需要$O(n)$，最终时间复杂度：$O(n × 2^n)$。????
空间复杂度：$O(n)$，递归深度为n，所以系统栈所用空间为$O(n)$，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为$O(n)$。

排列问题分析：

时间复杂度：$O(n!)$，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ….. 1 = n!。每个叶子节点都会有一个构造全排列填进数组的操作（对应的代码：result.push_back(path)），该操作的复杂度为$O(n)$。所以，最终时间复杂度为：n * n!，简化为$O(n!)$。
空间复杂度：$O(n)$，和子集问题同理。

组合问题分析：

时间复杂度：$O(n × 2^n)$，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
空间复杂度：$O(n)$，和子集问题同理。

一般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是一个概括吧！

关于去重

used数组
set集合
普通去重

子集问题2中使用了普通去重。

在全排列2中就使用了used数组去重，set集合去重写法如下：

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        unordered_set<int> uset; // 控制某一节点下的同一层元素不能重复
        for (int i = 0; i < nums.size(); i++) {
            if (uset.find(nums[i]) != uset.end()) {
                continue;
            }
            if (used[i] == false) {
                uset.insert(nums[i]); // 记录元素
                used[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

需要注意的是：使用set去重的版本相对于used数组的版本效率都要低很多

主要是因为程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。

使用set去重，不仅时间复杂度高了，空间复杂度也高了，在本周小结！（回溯算法系列三） (opens new window)中分析过，组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。

其他问题

括号生成

https://leetcode.cn/problems/generate-parentheses/submissions/

class Solution {
    public List<String> ans = new LinkedList();
    public void backTrack(int n, StringBuilder cur, int l_n, int r_n){
        if(n==0){
            if(l_n==r_n) ans.add(cur.toString());         // 有效的括号组合：左数量等于右数量
            return;
        }
        // 任何位置，左数量大于右数量
        if(l_n < r_n) return;
        // 生成左括号
        cur.append('(');
        backTrack(n-1, cur, 1+l_n, r_n);
        cur.deleteCharAt(cur.length()-1);
        // 生成右扩号
        cur.append(')');
        backTrack(n-1, cur, l_n, 1+r_n);
        cur.deleteCharAt(cur.length()-1);
    }
    public List<String> generateParenthesis(int n) {
        backTrack(2*n, new StringBuilder(), 0, 0);
        return ans; 
    }
}

这里的技巧在于用左右括号的数量来判断当前生成括号是否合法。

解数独

https://leetcode.cn/problems/sudoku-solver

class Solution {
    public boolean isValid(char[][] board, int r, int c, char ch){
        for(int i=0; i<9; ++i){
            if(board[r][i]==ch) return false;
            if(board[i][c]==ch) return false;
            if(board[3*(r/3)+i/3][3*(c/3)+i%3] == ch) return false;
        }
        return true;
    }
    public boolean backTrack(char[][] board, int i, int j){
        // 边界条件，换到下一行搜索
        if(j==9) return backTrack(board, i+1, 0);
        // 停止条件
        if(i==9) return true;
        if(board[i][j] != '.')
            return backTrack(board, i, j+1);
        else{
            // 遍历
            for(char k='1'; k<='9'; ++k){
                if(isValid(board, i, j, k)){
                    board[i][j] = k;
                    if(backTrack(board, i, j+1)) 
                        return true;
                    board[i][j] = '.';
                }
            }
        }
        return false;
    }
    public void solveSudoku(char[][] board) {
       backTrack(board, 0, 0); 
    }
}

代码看着简答，优化可不少：

1、 3x3宫格的有效性判断

2、先做有效性判断，再赋值这个格子；

2、backTrack的返回值是boolean且递归时用if判断，找到一个可行解就直接返回

雀魂启动

https://www.nowcoder.com/practice/448127caa21e462f9c9755589a8f2416

import java.util.*;

public class Main {
    static boolean flag;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int[] nums = new int[10];
        for (int i = 0; i < 13; i++) {
            nums[cin.nextInt()]++;
        }

        for (int i = 1; i <= 9; i++) {
            if (nums[i] <= 3) {
                int[] card = Arrays.copyOf(nums, nums.length); // 深拷贝一份card
                card[i]++;
                if (isHu(card, 1, 0, 0)) {
                    flag = true;
                    System.out.print(i + " ");
                }
            }
        }
        if(flag == false) // 不能和牌
            System.out.print(0);
    }

    public static boolean isHu(int[] card, int start, int quetou, int lian){
        if(start>=10){
            // 胡牌条件：1个雀头，4个顺子或刻子（这里我一起称之为lian）
            if(quetou==1 && lian==4) return true;
            else  //全部搜索完都没和牌 
                return false;
        }
        // 从start开始,用作雀头
        if(card[start]>=2 && quetou==0){
            card[start] -=2;
            if(isHu(card, start, 1, lian)) return true;
            card[start] +=2;
        }
        // 从start开始，用作刻子
        if(card[start]>=3){
            card[start] -=3;
            if(isHu(card, start, quetou, lian+1)) return true; 
            card[start] +=3;
        }
        // 从start开始，用作顺子
        if (start + 2 <= 9 && card[start] > 0 && card[start + 1] > 0 && card[start + 2] > 0){
            card[start]--;
            card[start + 1]--;
            card[start + 2]--;
            if(isHu(card, start, quetou, lian+1)) return true;
            card[start]++;
            card[start + 1]++;
            card[start + 2]++;
        }
        // 当前牌无法组成雀头、顺子或刻子，直接跳到下一个数额的牌
        if(isHu(card, 1+start, quetou, lian)) return true;
        return false;
    }
}

思路剖析：回溯法

1、手头有13张牌，向其中添加1张牌，看能否和牌；

2、遍历1-9大小的牌，每种数字的牌依次尝试用作雀头、顺子、刻子。

N皇后

https://leetcode.cn/problems/n-queens/submissions/

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

    public void backTrack(char[][] arrs, int n, int row){
        // 搜索到了最后一行
        if(row == n){
            // 收集结果
            List<String> tmp = new ArrayList<>();
            for(char[] arr: arrs){
                tmp.add(new String(arr));
            }
            ans.add(tmp);
            return;
        } 
        // row是当前行，对列进行搜索
        for(int col=0; col<n; ++col){
            if(isValid(arrs, row, col)){
                arrs[row][col] = 'Q';
                backTrack(arrs, n, 1+row);
                arrs[row][col] = '.';
            }
        }
    }

    public boolean isValid(char[][] arrs, int row, int col){
        int n =arrs.length;
        for(int i=0; i<arrs.length; ++i){
            if(arrs[row][i]=='Q') return false;
            if(arrs[i][col]=='Q') return false;
        }
        // 检查45度对角线, 只检查上半部分
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (arrs[i][j] == 'Q') {
                return false;
            }
        }
        // 检查135度对角线，只检查上半部分
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (arrs[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    public List<List<String>> solveNQueens(int n) {
        char[][] arrs  = new char[n][n];
        for(int i=0; i<n; ++i) Arrays.fill(arrs[i], '.');
        backTrack(arrs, n, 0);
        return ans;
    }
}

几个注意点：

1、用二维字符矩阵模拟棋盘，最后再转化为List<List<String>>

2、搜索时有顺序，先按行（自上而下），确定行后自左至右确定列

3、isValid先对未填时进行校验，而且只校验上半部分

–优化解法–：利用boolean数组表示已经占用的直线

回溯法总结

https://xyz.desirer233.fun/2024/06/04/数据结构与算法/Java回溯法/

作者

Desirer

发布于

2024-06-04

更新于

2024-06-04

回溯法总结

组合问题

组合

组合2

电话号码的数字组合

组合总和

组合总和2

切割

分割回文串

复原IP地址

子集问题

子集问题

子集问题2

递增子序列

排列

全排列问题

全排列问题2

中途休息

性能分析

关于去重

其他问题

括号生成

解数独

雀魂启动

N皇后

作者

发布于

更新于

许可协议

目录

分类