2020/3/20  打卡

题目

找出所有相加之和为 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]]

思路

一如既往的 DFS套路吧，进行回溯+剪枝。1.初试化结果数组res2.定义回溯函数help(count,i,tmp,target)，其中count表示当前已经使用的数字数，i表示当前访问的数字，tmp表示当前中间结果，target表示下一步的目标和。（1）若count==k，说明已经使用了k个数：若target==0，表示tmp的和等于n，将tmp加入res。return（2）遍历区间[i,10)[i,10)：*剪枝，若j>target，说明接下来的数字都比目标和大，break*执行回溯help(count+1,j+1,tmp+[j],target−j)3.执行help(0,1,[],n)4.返回res

代码

# 使用 dfs+剪枝的操作，对 数字数量进行限制。
# 时间复杂度为O(N!) 空间复杂度为O(k)
class Solution(object):def combinationSum3(self, k, n):""":type k: int:type n: int:rtype: List[List[int]]"""res = []# 内部dfs搜索 (count表示当前已经使用的数字数量，i表示当前访问的索引，tmp表示当前中间结果，target表示下一步的目标和)def dfs(count, i, tmp, target):# dfs截止的 边界条件 ，先是数量满足，再是和要对应if count == k:if target == 0:res.append(tmp)for j in range(i, 10):# 暴力之下的剪枝设定。if (j > target):break# 启动内部深搜索。  j+1是分支位置dfs(count + 1, j + 1, tmp + [j], target - j)# 外部启动dfs搜索dfs(0, 1, [], n)return res