代码随想录算法训练营第24天 |回溯基础理论、第77题. 组合、216.组合总和III、

回溯基础理论代码随想录
https://programmercarl.com/回溯算法理论基础.html#题目分类
第77题. 组合
https://leetcode.cn/problems/combinations/description/
代码随想录
https://programmercarl.com/0077.组合.html#算法公开课
第77题. 组合
https://leetcode.cn/problems/combinations/description/
代码随想录
https://programmercarl.com/0077.组合.html
17.电话号码的字母组合
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
代码随想录
https://programmercarl.com/0017.电话号码的字母组合.html#算法公开课

回溯搜索法 — 纯暴力搜索法

分类

1. 组合
2. 切割：回文子串
3. 子集问题 1234的子集
4. 排列问题：有顺序的组合
5. 棋盘问题

解决方式

抽象成树形结构递归（N叉树）

回溯法模版

while backtrack():
	if (终止条件)：
		收集结果；
		return
	for 节点 in (集合元素集)##：
		处理节点；
		递归函数；
		回溯操作；

1. 确定函数的参数；
2. 确定终止条件；
3. 确定单层搜索逻辑；

第77题. 组合

题解思路

• 参数：startindex（每次循环不断增加的值）,res（最终结果）,path(当前值)
• 剪枝：for i in range(start_index,n-(k-len(path))+1)
  • n-(k-len(path)):n可搜索空间；k-len(path)已经搜索过的空间；+1（除去startindex)

题解代码——优化后

class Solution:
    def back_track(self, n, k, start_index, res, path):
        if len(path)==k:
            res.append(path[:])
            return
        
        for i in range(start_index,n-(k-len(path))+2):
            path.append(i)
            self.back_track(n,k,i+1,res,path)
            path.pop()
            
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []
        self.back_track(n,k,1,res,path)
        return res

216.组合总和III

题解思路：

• 和上题一样 换成计算和而已
• 停止条件和优化也有变化

题解代码

class Solution:
    def back_track(self,k,n,index,res,path):
        if len(path)==k  and sum(path)==n:
            res.append(path[:])
            return
        for i in range(index,9-(k-len(path))+2):
            if sum(path)+i<=n:
                path.append(i)
                self.back_track(k,n,i+1,res,path)
                path.pop()
            else:
                break
                return

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        self.back_track(k,n,1,res,[])
        return res

17.电话号码的字母组合

题解思路

• 直接换index就可以解决循环嵌套问题 不需要循环两遍；

题解代码

class Solution:
    def __init__(self):
        self.map_ = {
            '2':['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']
        }
        self.res = []
        self.str = ""
    
    def back_trace(self,digits,index):
        if index==len(digits):
            self.res.append(self.str)
            return
        
        for i in self.map_[digits[index]]:#遍历每个字符串
            self.str = self.str + i
            self.back_trace(digits,index+1)#遍历每个按钮
            self.str = self.str[:-1]

    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return self.res
        self.back_trace(digits,0)
        return self.res