Combination Sum III
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.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
]
Example 2:
Input: k = 3, n = 9
Output:
, , ]
找出所有可能的组合,使组合中元素的个数等于k, 元素的和等于n。我们采用回溯法,当元素的个数为k并且和为9的时候我们记录这个结果,然后回溯,继续寻找其他可能的结果。代码如下:
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
LinkedList<Integer> list = new LinkedList<Integer>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
getCombinations(1, k, n, list, result);
return result;
}
public void getCombinations(int start, int k, int n, LinkedList<Integer> list, List<List<Integer>> llist) {
if(list.size() == k && n == 0) {
llist.add(new LinkedList<Integer>(list));
}
for(int i = start; i <= 9; i++) {
if(list.size() < k) {
list.add(i);
getCombinations(i + 1, k, n - i, list, llist);
list.removeLast();
}
}
}
}