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:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

找出所有可能的组合，使组合中元素的个数等于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();
            }
        }
    }
}