首页分享蓝桥杯第十天回溯法

蓝桥杯第十天回溯法

来源：花匠小妙招时间：2025-05-24 05:53

1.77. 组合 - 力扣（LeetCode） (leetcode-cn.com)

（1）常规

（2）剪枝

2.216. 组合总和 III - 力扣（LeetCode） (leetcode-cn.com)

（1）回溯法

（2）动态规划

3.17. 电话号码的字母组合 - 力扣（LeetCode） (leetcode-cn.com)

6.39. 组合总和 - 力扣（LeetCode） (leetcode-cn.com)

7.40. 组合总和 II - 力扣（LeetCode） (leetcode-cn.com)

8.131. 分割回文串 - 力扣（LeetCode） (leetcode-cn.com)

1.77. 组合 - 力扣（LeetCode） (leetcode-cn.com)

（1）常规

class Solution:

def combine(self, n: int, k: int) -> List[List[int]]:

results=[]

def back(result,length):

if length==k:

results.append(result)

return

if length==0:

start=1

else:

start=result[-1]

for i in range(start,n+1):

if i not in result:

back(result+[i],length+1)

back([],0)

return results

（2）剪枝

class Solution:

def combine(self, n: int, k: int) -> List[List[int]]:

results=[]

def back(result,length):

if length==k:

results.append(result)

return

if length==0:

start=1

else:

start=result[-1]+1

if k-length>n-start+1:return

for i in range(start,n+1):

if i not in result:

back(result+[i],length+1)

back([],0)

return results

2.216. 组合总和 III - 力扣（LeetCode） (leetcode-cn.com)

（1）回溯法

class Solution:

def combinationSum3(self, k: int, n: int) -> List[List[int]]:

results=[]

def dfs(result,length,sums):

if length==k:

if sums==n:

results.append(result)

return

if length==0:

start=1

else:

start=result[-1]+1

for i in range(start,10):

dfs(result+[i],length+1,sums+i)

return

dfs([],0,0)

return results

（2）动态规划

看不太懂这个东西，python的语法糖，有毒

class Solution:

def combinationSum3(self, k: int, n: int) -> List[List[int]]:

dp = [[[]] if j == 0 else [] for j in range(n + 1)]

for num in range(1, 10):

for j in range(n, num - 1, -1):

dp[j].extend(res + [num] for res in dp[j - num])

return [res for res in dp[-1] if len(res) == k]

3.17. 电话号码的字母组合 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:

def letterCombinations(self, digits: str) -> List[str]:

l=list(map(int,list(digits)))

index=[[]for i in range(10)]

init=97

for i in range(2,7):

for j in range(3):

index[i].append(chr(init))

init+=1

for j in range(4):

index[7].append(chr(init))

init+=1

for j in range(3):

index[8].append(chr(init))

init+=1

for j in range(4):

index[9].append(chr(init))

init+=1

results=[]

length=len(digits)

def dfs(curstr,depth):

if depth==length:

results.append(curstr)

return

nowc=l[depth]

for i in index[nowc]:

dfs(curstr+i,depth+1)

return

if len(digits)==0:

return results

dfs("",0)

return results

6.39. 组合总和 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

candidates.sort()

results=[]

def dfs(curlist,sums):

nonlocal results

if sums==target:

results.append(curlist)

return

if curlist==[]:

start=0

else:

start=candidates.index(curlist[-1])

for i in candidates[start:]:

if sums+i>target:continue

dfs(curlist+[i],sums+i)

return

dfs([],0)

return results

7.40. 组合总和 II - 力扣（LeetCode） (leetcode-cn.com)

精髓在for循环的第一句话

class Solution:

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

candidates.sort()

results=[]

def dfs(curlist,sums,lastindex):

nonlocal results

if sums==target:

results.append(curlist)

return

start=lastindex+1

for i in range(start,len(candidates)):

if i>start and candidates[i]==candidates[i-1]:

continue

if candidates[i]+sums>target:

continue

dfs(curlist+[candidates[i]],sums+candidates[i],i)

dfs([],0,-1)

return results

8.131. 分割回文串 - 力扣（LeetCode） (leetcode-cn.com)

很巧妙的切片

class Solution:

def partition(self, s: str) -> List[List[str]]:

results=[]

def dfs(rest,path):

if not rest:

results.append(path)

return

for i in range(len(rest)):

if rest[:i+1]==rest[:i+1][::-1]:

dfs(rest[i+1:],path+[rest[:i+1]])

dfs(s,[])

return results

蓝桥杯第十天回溯法