LeetCode刷题实战216:组合总和 III
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
题意
所有数字都是正整数。
解集不能包含重复的组合。
示例
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解题
class Solution {
private static List<List<Integer>> list;
private static List<Integer> tem;
public List<List<Integer>> combinationSum3(int k, int n) {
list = new ArrayList<List<Integer>>();
tem = new ArrayList<>();
dfs(k,n,0,0,1);
return list;
}
public void dfs(int k, int n,int sum,int cnt,int start) {
for (int i = start; i < 10; i++) {
if(sum+i > n || tem.size() > k) {
return;
}
tem.add(i);
if(sum+i == n && tem.size() == k) {
List<Integer> tem0 = new ArrayList<>();
tem0.addAll(tem);
list.add(tem0);
tem.remove(tem.size()-1);
return;
}
dfs(k,n,sum+i,cnt+1,i+1);
if(tem.size() > 0) {
tem.remove(tem.size()-1);
}
}
}
}
评论