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]]
题目标签：Array, Backtracking
题目给了我们 k 和 n， 让我们找到 从1到9里的 k 个数字组合，没有重复，加起来之和等于 n。这道题目与前面两个版本的基本思路一样，利用 backtracking来做，就是有一些条件不一样而已。这题规定了只能从1 到 9 里选数字，之前两个版本的题目都是给的array；还有就是 这一题 规定了我们 数字的数量要等于 k。所以只要做一些条件的修改就可以了，具体看code。
Java Solution:
Runtime beats 45.85%
完成日期：09/06/2017
关键词：Array，Backtracking
关键点：加入数字 -> 递归 -> 去除最后一个数字 来测试所有的组合可能性
class Solution
{
public List<List<Integer>> combinationSum3(int k, int n)
{
List<List<Integer>> list = new ArrayList<>();
int len = 10; // use only numbers from 1 to 9
backtrack(list, new ArrayList<>(), n, 1, len, k); return list;
} public boolean backtrack(List<List<Integer>> list, List<Integer> tempList,
int remain, int start, int len, int size)
{
if(remain < 0 || tempList.size() > size) // if remain less than 0 or number limit exceeds
return false; // no need to continue
else if(remain == 0 && tempList.size() == size) // only add tempList into list
{ // when remain = 0 and number limit size matches
list.add(new ArrayList<>(tempList));
return false;
}
else
{
for(int i=start; i<len; i++)
{
boolean flag;
tempList.add(i);
flag = backtrack(list, tempList, remain - i, i+1, len, size); // i + 1 because we cannot use same number more than once
tempList.remove(tempList.size() - 1); if(!flag) // if find a tempList answer or fail, no need to continue that loop
break; // because 1~9 is sorted and unique, the rest numbers are greater, they'll fail
} return true;
}
}
}
参考资料：N/A
LeetCode 算法题目列表 - LeetCode Algorithms Questions List