乌鲁木齐市网站建设_网站建设公司_移动端适配_seo优化

77. 组合

目标：
给定两个整数n和k，返回[1, n]中所有可能的k个数的组合。

• 组合：只关心选了哪些数
• 不关心顺序：[1,2]和[2,1]是同一个组合

核心思路

这是一个经典回溯 / DFS 组合题。

为什么用回溯？

• 我们在做的是：
  👉从 1~n 中“选 k 个”

• 每个数：

  • 要么选
  • 要么不选

• 但为了避免重复（比如[2,1]），必须保证递增顺序

回溯模型（记这个模板）

路径 path：当前已经选的数 起点 start：下一步可以选的最小数字（保证不回头） 终止条件：path 长度 == k

决策过程:

• 在[start, n]范围内枚举下一个数字
• 对每个数字：
  1. 选择它，加入path
  2. 递归继续选择下一个（start更新为当前数字 + 1）
  3. 回溯：撤销本次选择，尝试其他数字

代码

fromtypingimportListclassSolution:defcombine(self,n:int,k:int)->List[List[int]]:res=[]# 最终结果：存所有长度为 k 的组合path=[]# 当前正在构建的组合（回溯路径）defbacktracking(start):""" start：当前层允许选择的最小数字 保证组合中的数字递增，避免重复 """# 终止条件：已经选了 k 个数iflen(path)==k:# 注意：必须拷贝 path# 因为 path 会在回溯过程中被不断修改res.append(path[:])return# 在当前层，从 start 到 n 依次尝试每一个可能的选择foriinrange(start,n+1):# 1️⃣ 做选择：把当前数字加入路径path.append(i)# 2️⃣ 进入下一层递归# 下一层只能从 i + 1 开始选，不能回头backtracking(i+1)# 3️⃣ 撤销选择（回溯）# 把刚刚加进去的数字移除，尝试下一个 ipath.pop()# 从 1 开始尝试选第一个数backtracking(1)returnres

77剪枝做法

在已经不可能选满 k 个数的情况下，提前停止递归。

为什么 77 可以剪枝？

在某一层：

• 已经选了len(path)个数

• 还需要选：

  k-len(path)

  而当前能用的数字是：

  [start,start+1,...,n]

  数量是：

  n-start+1

  ❗ 如果：

  剩余可选数量 < 还需要选的数量

  👉 这条路不可能成功，直接停

剪枝怎么体现在代码里？

原来的 for 循环

foriinrange(start,n+1):

剪枝后的 for 循环（核心）

foriinrange(start,n-(k-len(path))+2):

如何理解：

我要给未来留下 足够的位置，让后面还能选满 k 个。

• 当前选i
• 后面最多还能选：

n-i

所以i最大只能到：

n-(k-len(path))+1

Python 的range右端不包含 → 再+1

代码

classSolution:defcombine(self,n:int,k:int):res=[]path=[]defbacktracking(start):# 如果已经选满 k 个，记录结果iflen(path)==k:res.append(path[:])return# 剪枝：# 剩余可选数量 = n - start + 1# 需要选的数量 = k - len(path)# 当剩余 < 需要时，for 循环根本不会进入foriinrange(start,n-(k-len(path))+2):path.append(i)backtracking(i+1)path.pop()backtracking(1)returnres

216.组合总和III

目标：
从1 到 9 中选 k 个不同的数，使它们的和等于 n，返回所有组合。

• 每个数字只能用一次
• 组合（不关心顺序）
• 数字范围固定是 1～9

核心思路

这是「固定长度 k 的组合」+「有目标和 n」
回溯设计（三要素）:

1. path
   • 当前选中的数字
   • 同时决定：
     • 已选个数len(path)
     • 当前和cur_sum
2. start
   • 下一步允许选择的最小数字
   • 保证递增，避免重复
3. 终止条件
   • 如果len(path) == k：
     • 若cur_sum == n→ 记录结果
     • 否则 → 直接返回

代码

fromtypingimportListclassSolution:defcombinationSum3(self,k:int,n:int)->List[List[int]]:res=[]# 存放所有满足条件的组合path=[]# 当前正在构建的组合defbacktracking(start):""" start: 当前层允许选择的最小数字 保证数字递增，避免重复使用同一个数字 """# 如果已经选了 k 个数iflen(path)==k:# 只在这里检查组合的和是否等于 nifsum(path)==n:# 必须拷贝 path，否则回溯时会被修改res.append(path[:])return# 从 start 到 9 依次尝试选择数字foriinrange(start,10):# 做选择：加入当前数字path.append(i)# 进入下一层，下一层只能选更大的数字backtracking(i+1)# 撤销选择（回溯）path.pop()# 从 1 开始尝试选第一个数字backtracking(1)returnres

216剪枝

✂️ 剪枝 1：和已经超过 n，直接停cur_sum > n

defbacktracking(start,cur_sum):ifcur_sum>n:# ✅ 剪枝 1return

如果当前路径的和已经大于目标 n，后面只会加更大的数，不可能成功 → 直接返回。

✂️ 剪枝 2：for 循环里提前 breaklen(path) > k

foriinrange(start,10):ifcur_sum+i>n:# ✅ 剪枝 2break

这行为什么是 break？

• i是递增的
• cur_sum + i已经超了
• 后面的i+1,i+2… 只会更大

👉 这一整段 for 都没必要继续

剪枝 1 和 剪枝 2 本质上在“做同一件事”（防止和超过 n），
但作用位置不同，功能并不完全重复。

👉 实际写代码时：二选一就够了
👉 最推荐：只保留剪枝 2

✂️ 剪枝 3：剩余数量不够凑满 k

# 还需要选的数量need=k-len(path)# 剩余可选数字数量remain=9-start+1ifremain<need:# ✅ 剪枝 3return

剩下的数字数量，已经不够凑满 k 个 👉 再选也没意义，直接停

代码

classSolution:defcombinationSum3(self,k:int,n:int):res=[]path=[]defbacktracking(start,cur_sum):# 🔴 剪枝 1：和已经超过 nifcur_sum>n:return# 选满 k 个数iflen(path)==k:ifcur_sum==n:res.append(path[:])return# 🔴 剪枝 3：剩余数字不够if9-start+1<k-len(path):returnforiinrange(start,10):# 🔴 剪枝 2：for 循环提前结束ifcur_sum+i>n:breakpath.append(i)backtracking(i+1,cur_sum+i)path.pop()backtracking(1,0)returnres

17.电话号码的字母组合

给一个字符串digits（只包含 2-9），每个数字对应手机九宫格字母，比如：

• 2: abc
• 3: def
• …
  把所有可能的字母组合都列出来。

例：
"23"→["ad","ae","af","bd","be","bf","cd","ce","cf"]
空输入""→ 返回[]

核心思路（回溯/DFS）

1. 用 dict 存数字 → 字母

   2->abc3->def...

2. 从左到右处理 digits

   • 第 1 个数字选一个字母
   • 第 2 个数字再选一个字母
   • 一直选到最后一位

3. 每一位都把能选的字母“试一遍”

   • 字符串长度够了 → 存结果
   • 不够 → 继续拼

状态：

• idx：当前处理到 digits 的第几位
• path：当前拼出来的字符串（或字符数组）

代码

fromtypingimportListclassSolution:defletterCombinations(self,digits:str)->List[str]:# 如果输入是空字符串，没有任何组合# LeetCode 要求返回 []ifnotdigits:return[]# 数字到字母的映射表（手机九宫格）phone={"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}res=[]# 最终结果：存所有字母组合path=[]# 当前正在拼的字符串（用 list，方便回溯）defbacktracking(idx):""" idx：当前处理到 digits 的第 idx 位 表示现在要给第 idx 个数字选一个字母 """# 如果已经处理完所有数字# 说明 path 中已经拼好了一个完整组合ifidx==len(digits):# 把当前拼好的字符列表转成字符串存起来res.append("".join(path))return# 取出当前数字对应的所有字母letters=phone[digits[idx]]# 依次尝试每一个字母forlinletters:# 1️⃣ 选择：把当前字母加入 pathpath.append(l)# 2️⃣ 进入下一位数字backtracking(idx+1)# 3️⃣ 撤销选择（回溯）# 换下一个字母继续试path.pop()# 从第 0 位数字开始处理backtracking(0)returnres

假设：

• m = len(digits)（digits 的长度）
• 每个数字最多对应 4 个字母（7 和 9）

为什么时间复杂度是这样：

• 第 1 位：最多 4 种选择
• 第 2 位：最多 4 种选择
• …
• 总组合数：4 × 4 × … × 4 = 4^m
• 每次存结果要"".join(path)，长度是m

👉 所以是4^m × m