【算法】回溯算法

g0dam

2024-11-29

Algorithm

回溯

回溯法概况

回溯法，一般可以解决如下几种问题：

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

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

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

`startIndex` 在回溯中的作用与用法

在 回溯（Backtracking） 相关的算法（如 子集、组合、排列、分割问题）中，startIndex 的作用非常重要，它决定了递归搜索的范围，影响 是否允许重复元素 以及 是否需要剪枝。

1. `startIndex` 作用

(1) 控制搜索范围，避免重复

startIndex 确保搜索从当前索引或后面的元素开始，防止回溯时重复选择之前已经选择过的元素。
适用于子集、组合问题，但 不适用于排列问题（排列问题允许元素交换顺序）。

(2) 递归层次推进

递归进入下一层时，startIndex 增加，确保搜索不回头，保证组合的唯一性。
startIndex 的值通常是 i + 1，表示当前元素 nums[i] 选中后，下次从 i+1 位置开始搜索。

2. `startIndex` 在不同回溯问题中的使用

(1) 组合问题（`startIndex` 需要）

问题：从 [1,2,3] 中选出长度为 2 的组合

class Solution:
    def combine(self, nums, k):
        result = []
        self.backtracking(nums, k, 0, [], result)
        return result

    def backtracking(self, nums, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        
        for i in range(startIndex, len(nums)):  # 关键：从 startIndex 开始
            path.append(nums[i])
            self.backtracking(nums, k, i + 1, path, result)  # 递归，i+1 避免重复选择
            path.pop()  # 回溯

sol = Solution()
print(sol.combine([1, 2, 3], 2))

📌 `startIndex` 的作用

避免重复选择：
- startIndex 让搜索从 i+1 位置开始，保证组合中的元素不重复使用。
输出结果
1
[[1,2], [1,3], [2,3]]
- **不会出现 [2,1] 或 [3,1]**，因为 startIndex 控制了搜索方向，确保元素不会向前选择。

(2) 排列问题（`startIndex` 不需要）

问题：从 [1,2,3] 中选出所有排列

class Solution:
    def permute(self, nums):
        result = []
        self.backtracking(nums, [], result)
        return result

    def backtracking(self, nums, path, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):  # 关键：不使用 startIndex
            if nums[i] in path:  # 不能重复使用元素
                continue
            path.append(nums[i])
            self.backtracking(nums, path, result)  # 递归，没有 startIndex
            path.pop()  # 回溯

sol = Solution()
print(sol.permute([1, 2, 3]))

📌 为什么不用 `startIndex`

排列问题允许元素交换顺序，所以不需要 startIndex 来限制搜索方向。
但仍然需要 if nums[i] in path: 这个条件，避免重复选择相同元素。
输出结果
1
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
- 这里 2,1 也出现了，说明 startIndex 没有限制排列顺序。

(3) 子集问题（`startIndex` 控制唯一性）

问题：求 [1,2,3] 的所有子集

class Solution:
    def subsets(self, nums):
        result = []
        self.backtracking(nums, 0, [], result)
        return result

    def backtracking(self, nums, startIndex, path, result):
        result.append(path[:])  # 子集问题可以随时收集结果

        for i in range(startIndex, len(nums)):  # 关键：避免重复选择
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)
            path.pop()  # 回溯

sol = Solution()
print(sol.subsets([1, 2, 3]))

📌 `startIndex` 作用

保证子集中的元素不重复
避免 [2,1] 这样的情况出现

输出结果

1	[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

3. `startIndex` 总结

问题	`startIndex` 是否需要	作用
组合（Combination）	✅ 需要	避免重复选择，控制搜索范围
排列（Permutation）	❌ 不需要	排列允许交换顺序，不限制搜索方向
子集（Subsets）	✅ 需要	避免重复选择，控制唯一性
回文分割（Palindrome Partitioning）	✅ 需要	控制切割点，避免重复分割

🚀 记住这条规则

如果问题允许元素交换顺序（如排列） → startIndex 不需要。
如果问题需要保证元素顺序（如组合、子集） → startIndex 需要。
如果是分割问题（如回文分割） → startIndex 也需要，控制切割点。

4. `startIndex` 与 `used` 数组的区别

有时候，在排列问题中，我们会用 used 数组代替 startIndex：

1	used = [False] * len(nums)

startIndex 作用 → 限制搜索范围，保证递增、不重复选择（用于组合、子集）。
used 作用 → 记录某个元素是否被用过，避免同层重复选择（用于排列、含重复元素的组合）。

例子：含重复元素的排列

class Solution:
    def permuteUnique(self, nums):
        result = []
        used = [False] * len(nums)
        nums.sort()  # 排序，方便去重
        self.backtracking(nums, [], used, result)
        return result

    def backtracking(self, nums, path, used, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:  # 这个元素已经被选过
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:  # 避免同层重复
                continue
            
            used[i] = True
            path.append(nums[i])
            self.backtracking(nums, path, used, result)
            path.pop()
            used[i] = False  # 回溯，撤销选择

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任何顺序返回答案。

直接想到的是for循环嵌套,但是如果k很大的话就会需要很多个for循环进行嵌套,这显然是不可能的,所以需要用到回溯算法.
递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。
组合问题可以抽象为树问题
但是回溯过程可以进行剪枝优化,如下图,n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。在第二层for循环，从元素3开始的遍历都没有意义了。

优化过程如下：
已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合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]。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    public void backtracking(int n, int k, int startIndex){
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            backtracking(n, k, i+1);
            path.removeLast();
        }
    }
}

216. 组合总和 III

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

只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

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

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

    private void backTracking(int targetSum, int k, int startIndex, int sum){
        // 剪枝
        if(sum > targetSum){
            return;
        }

        if(path.size() == k){
            if(sum == targetSum) result.add(new ArrayList<>(path));
            return;
        }

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

17.电话号码的字母组合

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

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

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

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

        String[] numString = {"", "", "abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTracking(digits, numString, 0);
        return list;
    }

    StringBuilder temp = new StringBuilder();

    public void backTracking(String digits, String[] numString, int num){
        if(num == digits.length()){
            list.add(temp.toString());
            return;
        }

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

39. 组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

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

        for(int i=idx; i < candidates.length; i++){
            if(sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum+candidates[i], i);  // 这道题的关键点在这里 i不用加1，所以可以重复选择i
            path.remove(path.size() - 1);
        }
    }
}

40.组合总和II

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

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

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

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

这道题目和39.组合总和 (opens new window)如下区别：
本题candidates 中的每个数字在每个组合中只能使用一次。
本题数组candidates的元素是有重复的，而39.组合总和 (opens new window)是无重复元素的数组candidates

我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
强调一下，树层去重的话，需要对数组排序！

如何判断同一树层上元素（相同的元素）是否使用过了呢。
如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] used;
    int sum = 0;

    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);
        return ans;
    }

    private void backtracking(int[] candidates, int target, int startIndex){
        if(sum == target){
            ans.add(new ArrayList(path));
        }

        for(int i = startIndex; i < candidates.length; i++){
            if(sum + candidates[i] > target){
                break;
            }
            if(i > 0 && candidates[i] == candidates[i - 1] && !used[i-1]){
                continue;
            }
            used[i] = true;
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, i+1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

下面这个是不使用used数组的版本

class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    int sum = 0;

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

    private void backtracking(int[] candidates, int target, int startIndex){
        if(sum == target){
            res.add(new ArrayList<>(path));
        }

        for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++){
            if(i > startIndex && candidates[i] == candidates[i-1]){
                continue;
            }

            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, i+1);

            int temp = path.getLast();
            sum -= temp;
            path.removeLast();
        }
    }
}

131. 分割回文串

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

示例 1：
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

## 基础版的代码
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        self.backtracking(s, 0, [], result);
        return result
    
    def backtracking(self, s, start_index, path, result):
        if start_index == len(s):
            result.append(path[:])
            return

        # 单层递归逻辑
        for i in range(start_index, len(s)):
            if self.is_palindrome(s, start_index, i):
                path.append(s[start_index:i+1])
                self.backtracking(s, i+1, path, result)
                path.pop()

    def is_palindrome(self, s:str, start:int, end:int) -> bool:
        i:int = start
        j:int = end
        while i<j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

上面的代码还存在一定的优化空间, 在于如何更高效的计算一个子字符串是否是回文字串。上述代码isPalindrome函数运用双指针的方法来判定对于一个字符串s, 给定起始下标和终止下标, 截取出的子字符串是否是回文字串。但是其中有一定的重复计算存在:
例如给定字符串”abcde”, 在已知”bcd”不是回文字串时, 不再需要去双指针操作”abcde”而可以直接判定它一定不是回文字串。
具体来说, 给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是s[0] == s[n-1]且s[1:n-1]是回文字串。
大家如果熟悉动态规划这种算法的话, 我们可以高效地事先一次性计算出, 针对一个字符串s, 它的任何子串是否是回文字串, 然后在我们的回溯函数中直接查询即可, 省去了双指针移动判定这一步骤.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        isPalindrome = [[False] * len(s) for _ in range(len(s))] # 初始化isPalindrome矩阵
        self.computePalindrome(s, isPalindrome)
        self.backtracking(s, 0, [], result, isPalindrome)
        return result

    def backtracking(self, s, startIndex, path, result, isPalindrome):
        if startIndex >= len(s):
            result.append(path[:])
            return

        for i in range(startIndex, len(s)):
            if isPalindrome[startIndex][i]:
                substring = s[startIndex:i+1]
                path.append(substring)
                self.backtracking(s, i+1, path, result, isPalindrome)
                path.pop()

    def computePalindrome(self, s, isPalindrome):
        for i in range(len(s) - 1, -1, -1): # # 需要倒序计算，保证在i行时，i+1行已经计算好了
            for j in range(i, len(s)):
                if j == i:
                    isPalindrome[i][j] = True
                elif j - i == 1:
                    isPalindrome[i][j] = (s[i] == s[j])
                else:
                    isPalindrome[i][j] = (s[i] == s[j] and isPalindrome[i+1][j-1])

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

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        self.backtracking(s, 0, 0, "", result)
        return result
    
    def backtracking(self, s, start_index, point_num, current, result):
        if point_num == 3: # 逗点数量为3时，分隔结束
            if self.is_valid(s, start_index, len(s) - 1): # 判断第四段子字符串是否合法
                current += s[start_index:]
                result.append(current)
            return

        for i in range(start_index, len(s)):
            if self.is_valid(s, start_index, i):
                sub = s[start_index:i+1]
                self.backtracking(s, i+1, point_num+1, current+sub+'.', result)
            else:
                break
        
    def is_valid(self, s, start, end):
        if start > end:
            return False
        if s[start] == '0' and start != end:
            return False
        num = 0
        for i in range(start, end+1):
            if not s[i].isdigit():
                return False
            num = num * 10 + int(s[i])
            if num > 255:
                return False
        return True

78. 子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

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

示例 2：
输入：nums = [0]
输出：[[],[0]]

这道题主要就是要遍历所有的路径而不需要减枝

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        self.backtracking(nums, 0, path, result)
        return result

    def backtracking(self, nums, startIndex, path, result):
        result.append(path[:])
        for i in range(startIndex, len(nums)):
            path.append(nums[i])
            self.backtracking(nums, i+1, path, result)
            path.pop()

90.子集II

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

示例:

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

这道题目和78.子集 (opens new window)区别就是集合里有重复元素了，而且求取的子集要去重。

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        self.backtracking(nums, 0, path, result)
        return result

    def backtracking(self, nums, startIndex, path, result):
        if len(path) > 1:
            result.append(path[:])
            # 注意这里不要return 因为需要取叶子上的节点

        uset = set()
        for i in range(startIndex, len(nums)):
            if (path and nums[i] < path[-1]) or nums[i] in uset:
                continue

            uset.add(nums[i])
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)
            path.pop()

也可以用哈希表也就是数组去重只要标记每个位置有没有用过就好了

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

输入：tickets = [[“MUC”,”LHR”],[“JFK”,”MUC”],[“SFO”,”SJC”],[“LHR”,”SFO”]]
输出：[“JFK”,”MUC”,”LHR”,”SFO”,”SJC”]

主要是构建邻接表，然后进行深度优先搜索

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        self.adj = {}
        tickets.sort(key=lambda x:x[1])

        for u, v in tickets:
            if u in self.adj: self.adj[u].append(v)
            else: self.adj[u] = [v]

        # 从JFK出发
        self.result = []
        self.dfs("JFK")

        return self.result[::-1]

    def dfs(self, s):
        while s in self.adj and len(self.adj[s]) > 0:
            # 找到s能到哪里,选第一个到的机场
            v = self.adj[s][0]
            self.adj[s].pop(0)
            self.dfs(v)
        self.result.append(s)

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def backtrack(row: int):
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    queens[row] = i
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    backtrack(row + 1)
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)

        solutions = list()
        queens = [-1]*n
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."]*n 
        backtrack(0)
        return solutions

37. 解数独

编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。N皇后问题 (opens new window)是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        row_used = [set() for _ in range(9)]
        col_used = [set() for _ in range(9)]
        box_used = [set() for _ in range(9)]
        for row in range(9):
            for col in range(9):
                num = board[row][col]
                if num == ".":
                    continue
                row_used[row].add(num)
                col_used[col].add(num)
                box_used[(row // 3)*3+col//3].add(num)
        self.backtracking(0, 0, board, row_used, col_used, box_used)

    def backtracking(self, row, col, board, row_used, col_used, box_used):
        if row == 9:
            return True

        next_row, next_col = (row, col+1) if col < 8 else (row + 1, 0)
        if board[row][col] != ".":
            return self.backtracking(next_row, next_col, board, row_used, col_used, box_used)

        for num in map(str, range(1,10)):
            if(num not in row_used[row] and num not in col_used[col] and num not in box_used[(row//3)*3+col//3]):
                board[row][col] = num
                row_used[row].add(num)
                col_used[col].add(num)
                box_used[(row//3)*3+col//3].add(num)
                if self.backtracking(next_row, next_col, board, row_used, col_used, box_used):
                    return True
                board[row][col] = "."
                row_used[row].remove(num)
                col_used[col].remove(num)
                box_used[(row//3)*3+col//3].remove(num)
        return False