题目描述
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
样例
输入: k = 3, n = 7
输出: [[1,2,4]]
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
算法1
(DFS + 回溯) $O(n * 2^n)$
强烈建议做这道题前先做LeetCode 39,40 题。
这道题的nums 数组其实给的比较隐晦:组合中只允许含有1-9 的正整数,其实就是一个nums{1,2,3,4,5,6,7,8,9} 数组。然后加上了一个条件:这个组合的长度只能 == 3,即k = 3, 其实这就是一个递归终止条件。加上另一个递归终止条件: target <= 0,共同组成一个递归终止条件而已。
时间复杂度
每个值都有两种状态: 2^n, 并且有n 个值, 所以整体时间复杂度: O(n * 2^n)
参考文献
Java 代码
public class 组合总和III {
int[] nums = new int[]{1,2,3,4,5,6,7,8,9};
List<List<Integer>> res = new ArrayList<>();
List<Integer> path;
public List<List<Integer>> combinationSum3(int k, int n) {
if(k == 0) return res;
path = new ArrayList<>();
dfs(this.nums,0,n,k);
return res;
}
void dfs(int[] nums,int index,int target,int k){
if(target <= 0 || path.size() == k){
if(target == 0 && path.size() == k){
res.add(new ArrayList<>(path));
}
return;
}
for(int i = index; i < nums.length; i++){
path.add(nums[i]);
dfs(nums,i + 1,target - nums[i],k);
path.remove(path.size() - 1);
}
}
}