【LeetCode】回溯算法类题目详解

所有题目均来自于LeetCode，刷题代码使用的Python3版本

image-20240305152953604

回溯算法

回溯算法是一种搜索的方法，在二叉树总结当中，经常使用到递归去解决相关的问题，在二叉树的所有路径问题中，我们就使用到了回溯算法来找到所有的路径。

回溯算法本质就是去穷举，性能并不是那么高效。一般为了提高效率，往往回溯算法会跟剪枝操作相结合。

回溯算法通常可以用来解决一些问题，这也是为什么会有回溯算法的原因

  • 组合问题
    • N个数里面按照一定规则找出k个数的集合。组合不强调元素的顺序
  • 切割问题
    • 一个字符串按一定规则有几种切割方式
      • 分割回文串
      • 复原IP地址
  • 子集问题
    • 一个N个数的集合里有多少符合条件的子集
  • 排列问题
    • N个数按照一定规则全排列，有几种排列方式。排列强调元素的顺序
  • 棋盘问题
    • N皇后、解数独问题

理解回溯

回溯法解决的问题都可以抽象为树形结构，回溯算法解决问题都是在集合中递归查找子集，集合的大小构成了树的宽度，递归的深度构成了树的深度。

递归必须要有终止条件，所以一定是一个高度有限的N叉树。

回溯模板

递归三部曲：

  • 返回值及参数
    • void backtracking(参数)
  • 回溯函数的终止条件
  • 回溯搜索的遍历过程
    • 回溯算法理论基础
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

练习题

77、组合

image-20231122103657483

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(n,k,startindex,path):
            if len(path)==k:
                # 这里需要注意，因为列表在Python中是可变数据类型，后面的修改会导致path变为[]
                res.append(path[:])
                return 
            # 这里的startindex代表的是在单层递归中需要遍历的次数 从startindex一直到n寻找符合条件的数
            for i in range(startindex, n+1):
                path.append(i)
                backtracking(n,k,i+1,path)
                a = path.pop()
        
        res = []
        backtracking(n,k,1,[])
        return res

image-20231122104026446

回溯+剪枝

使用剪枝的原理就在于如果剩余的元素个数已经小于k-len(path)的时候，我们就不再往下继续了。

  1. 已经选择过的元素个数：len(path)
  2. 还需要选择的个数：k-len(path)
  3. 在集合中更需要从最多要从下标为n-(k-len(path))+1开始遍历，在python中因为range循环的时候是左闭右开，所以还需要+1

77.组合4

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(n,k,startindex,path):
            if len(path)==k:
                # print(path)
                # 这里需要注意，因为列表在Python中是可变数据类型，后面的修改会导致path变为[]
                res.append(path[:])
                return 
           	
            for i in range(startindex, n-(k-len(path))+1+1):
                path.append(i)
                backtracking(n,k,i+1,path)
                # 回溯 退出上一个元素
                path.pop()
        
        res = []
        backtracking(n,k,1,[])
        return res

image-20231125142534496

2024更新代码：【传递的参数不要过多，题目已经给出的参数就不需要再进行传递了】

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def backtracking(startIndex, path):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(startIndex, n - (k - len(path)) + 1 + 1):
                path.append(i)
                backtracking(i + 1, path)
                path.pop()

        backtracking(1, [])
        return res

image-20240313130428518

216、组合总数III

image-20231122174951944

利用回溯代码模板。其中需要注意的是，如果path列表的和已经超过n，那么可以直接进行剪枝，除此之外，如果剩余的数字长度小于k-len(path)的话，就可以不用继续循环了，这一点也方便我们进行剪枝。

递归的三要素

  • 返回值和参数
def backtracking(n,k,startindex,path):
    pass
  • 递归终止条件
if sum(path)>n:
    return 
if len(path)==k and sum(path)==n:
    res.append(path[:])
    return
  • 递归体部分
for i in range(startindex,9 - (k - len(path)) + 1 + 1):
    path.append(i)
    backtracking(n,k,i+1,path)
    path.pop()

代码

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtracking(n,k,startindex,path):
            # 剪枝
            if sum(path)>n:
                return 
            if len(path)==k and sum(path)==n:
                res.append(path[:])
                return
            for i in range(startindex,9 - (k - len(path))+1+1):
                path.append(i)
                backtracking(n,k,i+1,path)
                path.pop()
        
        res = []
        backtracking(n,k,1,[])
        return res

17、电话号码的字母组合

image-20231122151406020

image-20231122151443212

思路

本题类似于组合问题，需要根据输入的数字对其能够涵盖的字母进行组合，需要解决下面几个问题：

  • 数字和字母如何进行映射
    • 采用一个列表，位置0和位置1的地方空出来，从2开始对应号码上的字母，用字符串表示
  • 两个字母两个for循环，三个字母三个for循环，多个字母多个for循环
  • 输入异常字母如何进行处理？
    • 对于空的digits需要返回一个空列表

递归三要素

  • 递归的参数

参数是digits和index，其中digits是题目给出的字符串，如“23”，而index是记录当前已经遍历到第几个数字了。【实际可以不用digits】

  • 递归结束的条件

如果index的长度和digits长度一样的话，直接return

if index==len(digits):
    res.append(path) # 这里的path被定义为字符串 而字符串在python中是不可变数据类型，因此可以直接用
    return
  • 递归体部分

需要注意的是，回溯的时候对于字符串要想去掉最后一个字符的方法是直接s=s[:-1]。

# 获取字符串中的数字
mynum = int(digits[index])
# 获取电话号码对应的字符组合
char = myhash[mynum]
for i in range(len(char)):
    path+=char[i]
    backtracking(digits, index+1, path)
    path = path[:-1] # 刨去字符串的最后一个字符

本题是不需要startindex的，因为遍历的不是同一个集合，而是不同的集合。在回溯问题中，如果是遍历同一个集合就需要传递一个参数startindex，用来表示的当前遍历到集合中的第几位。

本题通过index来判断目前遍历到第几个数字，并且index是通过充当函数的参数来实现的。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        myhash = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        res = []
        s = ""
        def backtracking(digits, index):
            nonlocal s
            if index==len(digits):
                res.append(s)
                return 
            # digit表示digits中的数字
            digit = int(digits[index])
            # letters表示digit所代表的数字对应的字母有哪些
            letters = myhash[digit]
            # for循环遍历这些字母 
            for i in range(len(letters)):
                s+=letters[i]
                # 进行回溯
                backtracking(digits,index+1)
                s = s[:-1]
        if len(digits)==0:
            return res
        backtracking(digits,0)
        return res

本题有一个需要特殊处理的地方，如果digits为空字符串的话，直接返回空列表，不需要在进行递归回溯了。

image-20231122151431566

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return []
        numList = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        res = []
        s = ""
        def backtracking(index):
            nonlocal s
            if len(digits) == len(s):
                res.append(s)
                return
            digit = int(digits[index])
            chars = numList[digit]
            for i in range(len(chars)):
                s+=chars[i]
                backtracking(index+1)
                s = s[:-1]
        backtracking(0)
        return res

39、组合总数

image-20231122222712060

image-20231122222723187

本题中说了candidates中的同一个数字可以无限制重复被选取，所以我们在进行递归的时候，传递的startindex就是i。

这里需要注意的是：每次需要传入startIndex的原因是可以避免选取之前已经取过的数字

39.组合总和

本题中需要注意及时剪枝（即当sum_>target之后就可以不用往下进行回溯了），并且可以使用一个累加的sum_代替掉使用内置的sum方法，节省时间开销。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        sum_ = 0

        def backtracking(startIndex, path):
            nonlocal sum_
            if sum_ > target:
                return
            if sum_ == target:
                res.append(path[:])
                return
            for i in range(startIndex, len(candidates)):
                path.append(candidates[i])
                sum_ += candidates[i]
                backtracking(i, path)
                sum_ -= path.pop()

        backtracking(0, [])
        return res

image-20231122222739974

40、组合总数II（*）

image-20231123110032934

本题需要注意的是，跟前面不同的地方在于每个数字在每个组合中只能使用一次，同时在解集中不能包含重复的组合。因此想到设置一个used数组来表示每个元素是否已经被访问过。 此处也可以不使用used数组

其中candidates数组需要进行排序，这样能够保证如果数字相同的情况下，只会使用一次。

40.组合总和II

要去重的是同一层上是否使用过，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

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

40.组合总和II1

img

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []  # 用于记录返回结果
        sum_ = 0
        def backtracking(candidates,target,path,startindex,used):
            nonlocal sum_
            if sum_>target:
                return 
            if sum_==target:
                res.append(path[:])
                return 
            for i in range(startindex,len(candidates)):
                if i>startindex and candidates[i]==candidates[i-1] and not used[i-1]:
                    continue
                path.append(candidates[i])
                sum_+=candidates[i]
                used[i]=True
                backtracking(candidates,target,path,i+1,used)
                sum_-=candidates[i]
                used[i]=False
                path.pop()
        # candidates需要进行排序，否则相同的数字可能不会连续
        candidates.sort()
        backtracking(candidates,target,[],0,[False]*len(candidates))
        return res

image-20231123110223652

优化 + 不使用used数组

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def backtracking(candidates,target,startindex,sum_,path):
            if sum_==target:
                res.append(path[:])
                return
            for i in range(startindex, len(candidates)):
                if i>startindex and candidates[i]==candidates[i-1]:
                    continue
                sum_+=candidates[i]
                # 这里进行判断，如果超过target则直接break 免去了后面的循环 节省时间开销	
                if sum_ > target:
                    break
                path.append(candidates[i])
                backtracking(candidates,target,i+1,sum_,path)
                sum_-=candidates[i]
                path.pop()
        candidates.sort()
        backtracking(candidates,target,0,0,[])
        return res

image-20231127100152702

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        sum_ = 0

        def backtracking(startIndex, path):
            nonlocal sum_
            if sum_ > target:
                return
            if sum_ == target:
                res.append(path[:])
                return
            for i in range(startIndex, len(candidates)):
                if i > startIndex and candidates[i] == candidates[i - 1]:
                    continue
                path.append(candidates[i])
                sum_ += candidates[i]
                backtracking(i + 1, path)
                sum_ -= path.pop()

        candidates.sort()
        backtracking(0, [])
        return res

131、分割回文串（*）

image-20231123151758868

本题递归结束的条件是当startindex==字符串s 的长度时，往结果集中添加数据并返回。

递归的参数是startindex，和path，需要进行递归的字符串为s[startindex:i+1]进行切片，同时本题要求是回文子串，所以还需要加上判断是否是回文数字，如果是回文数字才进行回溯，不是回文数字的话不进行任何操作。

在递归体部分，需要一个for循环，其遍历范围是startindex到len(s)，然后往path列表中添加的元素是s[startindex:i+1]，这里注意字符串的切片是左闭右开的，因此这里区间是i+1，然后递归进行遍历backtracking(s,i+1,path)，注意这里的startindex需要从i+1开始，这是因为根据题目的要求，不会有重复出现的子串。

在**【39、组合总数】**一题中，题目说明candidates中的元素是可以重复出现的，因此我们在进行递归的时候传入的startindex就为for循环遍历的层数i，这样就可以一直递归下去找到符合条件的答案。但是本题中不能出现重复的所以传入的参数是i+1

递归三要素

  • 参数和返回值
def backtracking(s, startindex, path):
  • 递归终止条件
if startindex==len(s):
    res.append(path[:])
    return
  • 递归体 单层搜索过程
for i in range(startindex,len(s)):
    if huiwen(s[startindex:i+1]):
        path.append(s[startindex:i+1])
        backtracking(s,i+1,path)
        path.pop()

全部代码：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        def backtracking(s,startindex,path):
            # print(startindex)
            # 如果分割到字符串末尾，则该轮结束
            if len(s)==startindex:
                res.append(path[:])
            
            for i in range(startindex,len(s)):
                # print(s[startindex:i+1])
                # 如果不是回文子串 不往path中添加
                if huiwen(s[startindex:i+1]):
                    path.append(s[startindex:i+1])
                    backtracking(s,i+1,path)
                    path.pop()
        
        def huiwen(s):
            return True if s==s[::-1] else False
            # i = 0
            # j = len(s)-1
            # while i<j:
            #     if s[i]!=s[j]:
            #         return False
            #     i+=1
            #     j-=1
            # return True
        
        backtracking(s,0,[])
        return res

image-20231125170244551

93、复原IP地址（*）

image-20231123215751666

image-20231123215802814

本题与分割字符串有几分相似，也属于分割问题。

递归三要素

  • 递归参数

字符串s，startindex和pointNum

pointNum表示IP地址中的.，如果有三个.的话，就说明当前的IP地址已经被分成四段了。

  • 递归结束的条件

根据本题要求，只要我们当前的字符串已经被分割成四段，即pointNum==3的时候，往res列表中添加结果并返回

  • 单层递归体中的操作
for i in range(startindex, len(s)):
    # IP 地址合法性剪枝
    if isValid(s[startindex:i+1]):
        sub = s[startindex:i+1]
        # 这里不能直接修改 path，而是使用一个副本进行传参
        backtracking(i + 1, path + sub + ".", pointNum + 1)
        else:
            break

img

校验逻辑：

  • 每一段以0开头则不合法
  • 每一段有非正整数数字不合法
  • 每一段数字如果大于255则不合法
def isValid(s):
    if len(s) == 0 or (s[0] == "0" and len(s) > 1) or int(s) > 255:
        return False
    return True

完整代码

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        def backtracking(startindex, path, pointNum):
            # 长度剪枝
            if len(s) - startindex > (4 - pointNum) * 3:
                return
            if len(s) - startindex < (4 - pointNum):
                return
            
            if pointNum == 3:
                if isValid(s[startindex:]):
                    res.append(path + s[startindex:])
                return
            
            for i in range(startindex, len(s)):
                # IP 地址合法性剪枝
                if isValid(s[startindex:i+1]):
                    sub = s[startindex:i+1]
                    # 这里不能直接修改 path，而是使用一个副本进行传参
                    backtracking(i + 1, path + sub + ".", pointNum + 1)
                else:
                    break
                
        def isValid(s):
            if len(s) == 0 or (s[0] == "0" and len(s) > 1) or int(s) > 255:
                return False
            return True

        backtracking(0, "", 0)
        return res

78、子集

image-20231124100225029

思路：

如果把子集问题抽象成一颗树的话，组合问题和分割问题都是收集树的叶子结点，子集问题是找树的所有结点。

78.子集

子集是无序的，{1,2}和{2,1}是等价的，也就是说之前取过的元素后面不会再取，因此在递归的过程中还需要传递一个参数startindex，每次都是从startindex继续往后进行搜索，而不是从0开始，如果是排列问题的话，for循环就要从0开始了，因为在排列中{1,2}和{2,1}是两个不一样的排列。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtracking(nums,startindex,path):
            res.append(path[:])
            # 这里不需要加递归结束的条件，当startindex达到len(nums)的时候程序也就自动返回了
            for i in range(startindex,len(nums)):
                path.append(nums[i])
                backtracking(nums,i+1,path)
                path.pop()
        backtracking(nums,0,[])
        return res

90、子集II（*）

image-20231124101803120

本题和上一题的区别在于nums数组中可能包含重复元素，我们首先将其进行排序，然后在往res列表中添加数据的时候，进行判断只有不在res列表中的结果才能添加进去。其余部分和上一题一样。

  • 使用in操作去重
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # nums = list(set(nums))
        res = []

        def backtracking(nums, startindex, path):
            if path not in res:
                res.append(path[:])
            if startindex>len(nums):
                return
            for i in range(startindex,len(nums)):
                path.append(nums[i])
                backtracking(nums,i+1,path)
                path.pop()
        nums.sort()
        backtracking(nums,0,[])
        return res

本题是树层去重，在同一层重复出现的需要去除重复值；树层去重的话需要对数组进行排序。

90.子集II

  • 直接判断去重
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(startIndex, path):
            res.append(path[:])
            for i in range(startIndex, len(nums)):
                if i > startIndex and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                backtracking(i + 1, path)
                path.pop()

        nums.sort()
        backtracking(0, [])
        return res
  • 使用used数组去重（推荐）
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False]*len(nums)

        def backtracking(nums,startindex,path,used):
            res.append(path[:])
            if startindex > len(nums):
                return 
            for i in range(startindex,len(nums)):
                if i>0 and nums[i]==nums[i-1] and not used[i-1]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking(nums,i+1,path,used)
                used[i] = False
                path.pop()
        nums.sort()
        backtracking(nums,0,[],used)
        return res

90.子集II

491、递增子序列（*）

image-20231124211319729

本题需要再输入的序列中找到全部的递增子序列，同时需要注意的是题目中输入的数组会包含重复的元素，并且说明如果出现两个整数相等也会看作是递增序列的一种特殊情况。

利用回溯的思路，我们写出递归的三要素：

  • 参数和返回值

参数有：startindex用于记录下一层遍历的起始位置； path 用于记录结果列表

def backtracking(startindex, path):
  • 递归终止条件

题目中要求递增子序列中至少2个元素，因此可以判断如果len(path)>1则往res列表中添加结果并返回

这里需要注意，不能加return，加上了return的话，就会导致同一个树枝上的其他结果不能得到保存，这点类似于子集问题，子集问题是需要寻找叶子上的节点。

if len(path)>1:
    res.append(path[:])
    # return
  • 单层搜索逻辑

本题需要寻找递增子序列，不像之前的题目可以直接通过排序解决去重问题，因此需要使用另一种去重的方式，使用python中的集合，在Python中集合也是一个哈希表，可以在O(1)时间复杂度查询到想要的结果。

这里注意条件是和递增是或者or的关系的，即如果该数字已经在uset中，说明已经使用过了，需要跳过该数字。

同时uset是在每一层都会重新进行定义的，uset只会负责本层的结果。同一个父节点下的一层内如果出现重复数字则直接跳过

这里的一层指的是节点拥有同一个父节点

491. 递增子序列1

uset = set()
for i in range(startindex, len(nums)):
    if (path and path[-1]>=nums[i]) or nums[i] in uset:
        continue
    uset.add(nums[i])
    path.append(nums[i])
    backtracking(nums,i+1,path)
    path.pop()

完整代码：

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(startIndex, path):
            if len(path) > 1:
                res.append(path[:])
            uset = set()
            for i in range(startIndex, len(nums)):
                if (path and path[-1] > nums[i]) or nums[i] in uset:
                    continue
                uset.add(nums[i])
                path.append(nums[i])
                backtracking(i + 1, path)
                path.pop()

        backtracking(0, [])
        return res

image-20231124213406251

46、全排列

image-20231124214516935

全排列和组合问题、切割问题以及子集问题的区别就在于每次遍历都需要从0开始，而不是传进来的startindex，也就是说全排列问题中是不需要startindex的。

另外在之前的几种问题中，有几个我们传入参数不是i+1而是i的，这是因为题目中说明可以出现重复元素。如果要求是不能出现重复元素的话，只能传入i+1。

本题中因为下标都是从0开始进行遍历的，所以就需要记录哪些数字之前已经被使用过了，所以这里有两个方法：

  • 使用used数组进行记录
  • 使用uset集合进行记录

上面的这两种方法都需要在函数的参数中进行传递

递归三部曲

  • 参数和返回值
def backtracking(path,used):
  • 递归终止条件
if len(path)==len(nums):
    res.append(path[:])
    return
  • 单层搜索逻辑
for i in range(0, len(nums)):
    if used[i]:
    	continue
    used[i]=True
    path.append(nums[i])
    backtracking(nums,path)
    used[i]=False
    path.pop()

完整代码：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)

        def backtracking(path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking(path, used)
                path.pop()
                used[i] = False

        backtracking([], used)
        return res

image-20231125112358453

使用uset集合避免使用个重复的数组

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(path, uset):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if nums[i] in uset:
                    continue
                uset.add(nums[i])
                path.append(nums[i])
                backtracking(path, uset)
                uset.remove(path.pop())

        backtracking([], set())
        return res

image-20240319092628141

47、全排列II（*）

image-20231124215605773

本题因为nums中包含重复的数字，因此需要去重，去重的时候因为需要判断相邻的两个数是否相等，所以在一开始需要对nums进行排序。【排序和重复数字去重是一个配套操作需要一起来】

之后本题的和全排列的区别就在于需要判断相邻的两数是否相等并且前一个数是否没有用过。

for循环是横向遍历，递归是纵向遍历（即沿着树枝进行遍历的效果）

img

used数组主要使用来记录哪些元素已经使用过了，全排列问题中元素不能重复使用，每个元素都只能适用一次。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtracking(path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                if used[i]:
                    continue
                path.append(nums[i])
                used[i] = True
                backtracking(path, used)
                path.pop()
                used[i] = False

        nums.sort()
        backtracking([], [False] * len(nums))
        return res

组合问题和排列问题是在树形结构的叶子结点上收集结果，而子集问题就是取树上所有结点的结果。

and not used[i - 1]这部分代码是用来跳过重复的数字，如果前一个数字没有被选取，并且和当前数字值一致，则可以跳过这部分，这样的操作可以避免答案中出现重复的值。

使用uesd数组进行去重：
img

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False] * len(nums)

        def backtracking(path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i in range(len(nums)):
                if i>0 and nums[i]==nums[i-1] and not used[i-1]:
                    continue
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtracking(path, used)
                used[i] = False
                path.pop()

        nums.sort()
        backtracking([], used)
        return res

image-20231125112843814

784、字母大小写全排列

322、重新安排行程（hard)

image-20231127103728274

51、N皇后

image-20231127111457348

递归参数

定义res来存放最终的结果，n棋盘大小，row记录当前遍历到棋盘的第几层

递归终止条件

51.N皇后

当递归到叶子结点的时候就可以收集结果了。

if row==n:
    res.append(chessboard)
    return ;

单层递归逻辑

遍历这个棋盘的每一行，在python中，二维数组的表示就用嵌套列表表示即可。

验证棋盘是否合法

  • 皇后不能同行
  • 皇后不能同列
  • 皇后不能斜对角线（45度和135度）
def isValid(row, col, chessboard):
            # 列检查
            for i in range(row):
                if chessboard[i][col] == "Q":
                    return False
            # 45°角检查 这里的检查是从row col往前找
            i,j = row-1,col-1
            while i>=0 and j>=0:
                if chessboard[i][j] == "Q":
                    return False
                i-=1
                j-=1
            
            # 135°角检查
            i,j = row-1, col+1
            while i>=0 and j<len(chessboard):
                if chessboard[i][j]=="Q":
                    return False
                i -= 1
                j += 1
            return True

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:    
        def backtracking(n,row,chessboard):
            # 递归终止的条件 当递归参数row==n时就进行发返回 并将结果添加到res中
            if row==n:
                res.append(chessboard[:])
                return
            # 对棋盘的每一行进行操作 判断是否合法
            for col in range(n):
                if isValid(row,col,chessboard):
                    chessboard[row] = chessboard[row][:col] + "Q" + chessboard[row][col+1:]
                    backtracking(n,row+1,chessboard)
                    chessboard[row] = chessboard[row][:col] + "." + chessboard[row][col+1:]
        
        def isValid(row, col, chessboard):
            # 列检查
            for i in range(row):
                if chessboard[i][col] == "Q":
                    return False
            # 45°角检查 这里的检查是从row col往前找
            i,j = row-1,col-1
            while i>=0 and j>=0:
                if chessboard[i][j] == "Q":
                    return False
                i-=1
                j-=1
            
            # 135°角检查
            i,j = row-1, col+1
            while i>=0 and j<len(chessboard):
                if chessboard[i][j]=="Q":
                    return False
                i -= 1
                j += 1
            

            return True
        
        res = []
        chessboard = ["."*n for _ in range(n) ]
        print(chessboard)
        backtracking(n,0,chessboard)
        return res

解数独

回溯总结

需要startIndex的题目有：

需要return的情况有：

一般情况下，如果题目中要求不能出现重复的数据，需要搭配这used数组进行使用，除此之外还需要对集合进行一个排序，这样可以在值相同的情况下进行判断。

if i>0 and nums[i]==nums[i-1] and not used[i-1]:
    continue

used[i-1]==False 说明在同一层的前面结点已经使用过该数据了，后面不需要重复进行操作。

如果集合中存在重复的数字序列，则需要对其进行排序

  • 组合总数II
  • 子集II
  • 全排列II

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/536914.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

淘宝1688京东店铺所有商品数据接口（item_search_shop接口系列，可测试）

淘宝1688京东店铺所有商品数据接口（item_search_shop接口系列，可测试）

淘宝、1688和京东都提供了API接口供开发者调用&#xff0c;以获取店铺和商品的详细数据。对于您提到的item_search_shop接口系列&#xff0c;这主要是用于获取店铺所有商品的数据。然而&#xff0c;具体的接口名称和功能可能会因平台而异&#xff0c;且可能随着平台的更新而有所…
阅读更多...
LigaAI x 极狐GitLab，共探 AI 时代研发提效新范式

LigaAI x 极狐GitLab，共探 AI 时代研发提效新范式

近日&#xff0c;LigaAI 和极狐GitLab 宣布合作&#xff0c;双方将一起探索 AI 时代的研发效能新范式&#xff0c;提供 AI 赋能的一站式研发效能解决方案&#xff0c;让 AI 成为中国程序员和企业发展的新质生产力。 软件研发是一个涉及人员多、流程多、系统多的复杂工程&#…
阅读更多...
微服务面试题二

微服务面试题二

1.什么是雪崩 微服务之间相互调用&#xff0c;因为调用链中的一个服务故障&#xff0c;引起整个链路都无法访问的情况。 如何解决雪崩&#xff1f; 超时处理&#xff1a;请求超时就返回错误信息&#xff0c;不会无休止等待仓壁模式&#xff1a;限定每个业务能使用的线程数&a…
阅读更多...
cordova后台插件开发新手教程

cordova后台插件开发新手教程

typora-root-url: imags cordova后台插件开发新手教程 预安装环境&#xff1a;JDK11、Android studios、nodo.js 一、环境搭建 1.安装Cordova npm install -g cordova2.创建项目 cordova create 具体命令&#xff1a; cordova create 目录名 包名 项目名 执行结果终端&am…
阅读更多...
大模型RAG（三）检索环节（Retriever）

大模型RAG（三）检索环节（Retriever）

1. 搜索索引 &#xff08;1&#xff09;向量存储索引 最原始的实现是使用平面索引 — 查询向量和所有块向量之间的暴力计算距离。根据索引选择、数据和搜索需求&#xff0c;还可以存储元数据&#xff0c;并使用元数据过滤器来按照日期或来源等条件进行信息检索。LlamaIndex 支…
阅读更多...
【实战JVM】打破双亲委派机制之线程上下文类加载器

【实战JVM】打破双亲委派机制之线程上下文类加载器

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…
阅读更多...
CS与MSF联动/shell互相反弹

CS与MSF联动/shell互相反弹

Cs的shell反弹到msf 参考资料:https://blog.csdn.net/Zlirving_/article/details/113862910 先建立监听器 先建立一个监听器&#xff0c;和msf的要一一对应&#xff0c;上面的ip必须是可以ping通的大部分情况是外网ip Msf&#xff1a; use exploit/multi/handler set paylo…
阅读更多...
Netty学习——实战篇1 BIO、NIO入门demo 备注

Netty学习——实战篇1 BIO、NIO入门demo 备注

1 BIO 实战代码 Slf4j public class BIOServer {public static void main(String[] args) throws IOException {//1 创建线程池ExecutorService threadPool Executors.newCachedThreadPool();//2 创建ServerSocketServerSocket serverSocket new ServerSocket(8000);log.in…
阅读更多...
高清无水印短视频素材去哪找？今天讲五个素材网站，记得收藏

高清无水印短视频素材去哪找？今天讲五个素材网站，记得收藏

在视频剪辑的世界里&#xff0c;我就像是那个经常带着一副老花镜在宝藏地图上寻宝的老海盗。每次寻宝之旅&#xff0c;我都能从九才素材网这个家门口的宝藏开始&#xff0c;然后驾驶我的老旧剪辑船&#xff0c;航向国际的深蓝大海&#xff0c;寻找那些只属于知情者的秘密宝藏。…
阅读更多...
【C++进阶】C++异常详解

【C++进阶】C++异常详解

C异常 一&#xff0c;传统处理错误方式二&#xff0c;C处理的方式三&#xff0c;异常的概念四&#xff0c;异常的使用4.1 异常和捕获的匹配原则4.2 函数调用链中异常栈展开匹配原则4.3 异常的重新抛出&#xff08;异常安全问题&#xff09;4.4 RAII思想在异常中的作用 五&#…
阅读更多...
使用Java+Maven+TestNG进行自动化测试

使用Java+Maven+TestNG进行自动化测试

写作背景&#xff1a;有点Java基础的功能测试人员&#xff08;点点点工程师&#xff09;&#xff0c;所在项目有"去QE"的趋势&#xff0c;所以自己要多点亮其他技能&#xff0c;让路子走宽点。 简单说一下去QE&#xff1a;项目测试不再有专职的测试工程师来做&#x…
阅读更多...
计算机网络——40各个层次的安全性

计算机网络——40各个层次的安全性

各个层次的安全性 安全电子邮件 Alice需要发送机密的报文m给Bob Alice 产生随机的对称秘钥&#xff0c; K s K_s Ks​使用 K s K_s Ks​对报文进行加密&#xff08;为了效率&#xff09;对 K s K_s Ks​使用Bob的公钥进行加密发送 K s ( m ) K_s(m) Ks​(m)和 K B ( K S ) K…
阅读更多...
小程序/app/H5多端圈子社区论坛系统交友/社交/陌生人社交即时聊天私域话题社区论坛 行业圈子小程序 微信社区小程序圈子论坛社区小程序

小程序/app/H5多端圈子社区论坛系统交友/社交/陌生人社交即时聊天私域话题社区论坛 行业圈子小程序 微信社区小程序圈子论坛社区小程序

项目介绍 这是一个社区论坛类小程序项目源码&#xff0c;可以实现用户发送自定义图文内容&#xff0c;点赞&#xff0c;评论&#xff0c;回复&#xff0c;记录评论过的帖子&#xff0c;记录发表过的帖子&#xff0c;左滑删除&#xff0c;在线实时接收消息&#xff0c;离线接收…
阅读更多...
MySQL高级篇（索引概述、优缺点、结构 B+Tree）

MySQL高级篇（索引概述、优缺点、结构 B+Tree）

目录 1、索引概述 2、索引优缺点 3、索引的结构 1、索引概述 介绍&#xff1a;索引&#xff08;index&#xff09;是帮助MySQL 高效获取数据 的 数据结构&#xff08;有序&#xff09;。在数据之外&#xff0c;数据库系统还维护着满足特定查找算法的数据结构&#xff0c;这些数…
阅读更多...
分布式系统：缓存与数据库一致性问题

分布式系统：缓存与数据库一致性问题

前言 缓存设计是应用系统设计中重要的一环&#xff0c;是通过空间换取时间的一种策略&#xff0c;达到高性能访问数据的目的&#xff1b;但是缓存的数据并不是时刻存在内存中&#xff0c;当数据发生变化时&#xff0c;如何与数据库中的数据保持一致&#xff0c;以满足业务系统…
阅读更多...
java实现TCP交互

java实现TCP交互

服务器端 import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.net.ServerSocket; import java.net.Socket; import java.util.PriorityQueue; import java.util.Scanner;public class TCP_Serv…
阅读更多...
(文章复现)考虑网络动态重构的分布式电源选址定容优化方法

(文章复现)考虑网络动态重构的分布式电源选址定容优化方法

参考文献&#xff1a; [1]朱俊澎,顾伟,张韩旦,等.考虑网络动态重构的分布式电源选址定容优化方法[J].电力系统自动化,2018,42(05):111-119. 1.摘要 以投资周期经济收益最高为目标&#xff0c;基于二阶锥规划提出了一种考虑网络动态重构的分布式电源选址定容优化方法。首先&am…
阅读更多...
OpenStack （T）部署trove

OpenStack （T）部署trove

环境&#xff1a;Openstack&#xff08;T&#xff09; CentOS Linux release 7.9.2009 (Core) 正文&#xff1a; 1.控制节点安装trove软件包 # yum install openstack-trove-guestagent openstack-trove python-troveclient openstack-trove-ui –y2.创建数据库&#xff0c…
阅读更多...
动态代理 --java学习笔记

动态代理 --java学习笔记

什么是动态代理&#xff1f; 当一个类的很多方法都存在重复冗杂的部分&#xff0c;就可以使用代理来处理那些重复部分的任务&#xff0c;到了各自的实现部分再丢回给原方法处理&#xff0c;同时也可以提高方法的扩展性&#xff0c;而动态则是指在运行时动态地创建代理对象&…
阅读更多...
【高德地图笔试题汇总】2024-04-11-高德地图春招笔试题-三语言题解(CPP/Python/Java)

【高德地图笔试题汇总】2024-04-11-高德地图春招笔试题-三语言题解(CPP/Python/Java)

&#x1f36d; 大家好这里是KK爱Coding &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新高德地图近期的春秋招笔试题汇总&#xff5e; &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&…
阅读更多...
最新文章

Copyright @ 2022~2023