77. 组合
分析代码
通过截图 代码（剪枝）
通过截图 216. 组合总和 III
分析代码（暴力回溯）
通过截图 代码（限制住path的长度）
通过截图 代码（剪去一部分横向遍历的枝）
通过截图 代码（用Sum记录path里面的和）
通过截图 代码（对>n的进行剪枝）
通过截图
77. 组合给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1： 输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例 2： 输入：n = 1, k = 1 输出：[[1]] 提示： 1 <= n <= 20 1 <= k <= n分析
1.直接使用回溯法去做
2.剪枝（优化方法，减少不必要的搜索）
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def backtrack(n,k,start):
if len(path) == k: # 终止条件
# 不能直接添加path，因为列表是可变对象，进行append，pop()操作会使res发生变化
res.append(path[:])
return
for i in range(start,n+1): # 未选择的范围
path.append(i)
backtrack(n,k,i+1)
path.pop() # 回溯
backtrack(n,k,1)
return res
通过截图
代码（剪枝）
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def backtrack(n,k,start):
if len(path) == k:
res.append(path[:])
return
for i in range(start,n-(k-len(path))+2):
# k-len(path):未选择的元素个数
# n-(k-len(path))+1:至多开始的遍历元素
path.append(i)
backtrack(n,k,i+1)
path.pop()
backtrack(n,k,1)
return res
通过截图
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 说明： 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]分析
1.暴力回溯，突然发现k的范围没有限制住，即path里一直添加删除，算了非常多不必要的东西，假如我k=2,然后数的范围只能取1到4，限制了k的话（暂时不做剪枝）遍历的只有1个和2个数组成的集合；如果没限制住k，他会不断添加，先添加到四个，回退到三个，两个，不断判断，即由1,2,3,4任意数字所组成的所有子集都会被遍历一遍。（由于此题的特殊性：每个数字只能用一次，最多就用九次，所以暴力还是可以过关的）
2.在1的基础上限制住path的长度
3.在2的基础上剪去横向遍历的无用枝（比如说k=3,那么数的选择至多到7）
4.内置函数sum计算每次都得重新计算（虽然此题规模不大，但可以通过此改进优化时间），用一个变量储存总和，回溯时减去
5.在前面的基础上，如果Sum>n,剪枝
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
path = []
def backtrack(k,n,start):
if len(path) == k and sum(path) == n:
res.append(path[:])
return
for i in range(start,10):
path.append(i)
backtrack(k,n,i+1)
path.pop()
backtrack(k,n,1)
return res
通过截图
代码（限制住path的长度）
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
path = []
def backtrack(k,n,start):
if len(path) == k:
if sum(path) == n:
res.append(path[:])
return
for i in range(start,10):
path.append(i)
backtrack(k,n,i+1)
path.pop()
backtrack(k,n,1)
return res
通过截图
代码（剪去一部分横向遍历的枝）
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
path = []
def backtrack(k,n,start):
if len(path) == k:
if sum(path) == n:
res.append(path[:])
return
for i in range(start,9-(k-len(path))+2):
path.append(i)
backtrack(k,n,i+1)
path.pop()
backtrack(k,n,1)
return res
通过截图
代码（用Sum记录path里面的和）
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
path = []
def backtrack(k,n,start,Sum):
if len(path) == k:
if Sum == n:
res.append(path[:])
return
for i in range(start,9-(k-len(path))+2):
path.append(i)
Sum+=i
backtrack(k,n,i+1,Sum)
path.pop()
Sum-=i
backtrack(k,n,1,0)
return res
通过截图
代码（对>n的进行剪枝）
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
path = []
def backtrack(k,n,start,Sum):
if len(path) == k:
if Sum > n:
return
if Sum == n:
res.append(path[:])
return
for i in range(start,9-(k-len(path))+2):
path.append(i)
Sum+=i
backtrack(k,n,i+1,Sum)
path.pop()
Sum-=i
backtrack(k,n,1,0)
return res
通过截图
如有错误，敬请指正，欢迎交流，谢谢♪(･ω･)ﾉ
