Problem
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
1 | Input: k = 3, n = 7 |
Example 2:
1 | Input: k = 3, n = 9 |
Note:
- All numbers will be positive integers.
- The solution set must not contain duplicate combinations.
Analysis
这道题目要求我们用k
个数字相加得到某个给定的值n
,数字选择的范围是1-9
,要返回所有的组合。同时还要求一个数字最多只能出现一次,所以再每次选择的时候不能考虑之前已经使用过的数字了。
这道题目的做法毫无疑问是递归,因为父问题和子问题是一样的,以example1为例,当第一次选择了1之后,那么问题就变为k=2
和n=6
了,这就是很明显使用递归的特征。
选择好大致的方法后,就来看一下每个递归内要做什么了,首先是上面提到的数字选择的范围,因为要保证唯一性,所以我们干脆就从1开始选,选完之后下一个递归就不能选了,这个信息需要在递归中传递。然后就是要解决example2中[1,2,6]
和[1,3,5]
这种情况,在考虑第二种情况的时候,选了1一直需要跳过2才能选到3,怎么实现这种呢?实际上这个就有点DFS的味道了,开始递归就是DFS,然后完成一个之后就把刚刚选中的取消掉,换下一个。
判断是否结束也很容易,如果n < 0
说明减成负数了,该组合的数字之和就不是目标数字,如果n = 0 && temp.size() == k
,说明刚好k个数字之和是n,这个就是正确答案了。
Solution
递归的时候要带上可选数字的范围信息(start)和正在计算的组合,当然还有总的答案。
Code
1 | class Solution { |
Summary
这道题目首先要看得出是用递归,要找出父问题如何变成子问题的。然后是考虑多种组合的情况,再根据这些情况看看递归过程中需要什么信息,在递归的时候带上就可以了。这道题的分析到这里,谢谢!