蓝桥杯 第十天 回溯法

蓝桥杯 第十天 回溯法

目录

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