问题描述
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:
Input:
k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input:
k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
问题分析
给定两个数，第一个数表示一个集合中包括的数值的个数，第二个数表示和。其中集合中的数只能是1~9。用深度优先遍历，列出所有序列，然后过程中将一些不符合条件的分支及时的给剪除，类似于fail-fast。
实现代码
/**
* 找出 n 个 数的和 等于K
* 这个题的答案是 1-k中n个数的集合的和 等于 k。
* 这个题目应该是用DFS外加剪枝法来解决问题。
*
* @param k 数值的和
* @param n 数字的个数
* @return
*/
public List<List<Integer>>
combinationSum3(
int k,
int n) {
List<List<Integer>> resultList =
new ArrayList<List<Integer>>();
DFS(resultList,
new ArrayList<Integer>(),
1,
10, k, n);
return resultList;
}
/**
* @param result 结果序列
* @param resultList 所有结果序列
* @param start 最小的值
* @param end 最大的值
* @param count 值的个数
* @param sum 和
*/
private void DFS(List<List<Integer>> resultList, List<Integer> result,
int start,
int end,
int count,
int sum) {
if (sum ==
0 && count ==
0) {
resultList.add(
new ArrayList<Integer>(result));
return;
}
for (
int i = start; i < end; i++) {
if (i > sum || count <=
0) {
return;
}
else {
result.add(i);
DFS(resultList, result, i +
1, end, count -
1, sum - i);
result.remove(result.size() -
1);
}
}
}
总结
这里使用了递归的方法，非常的好用。
