leetcode216.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.


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个不同数字的组合，这些组合中数字的和为n

参考Combination Sum I ，Combination Sum II

解答

这是一道典型的backtracking的题目，通过递归的方式记录尝试的节点，如果成功则加入结果集，如果失败则返回上一个尝试的节点进行下一种尝试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    combinationSum3(k,n,1,result, new ArrayList<Integer>());
    return result;
}

public void combinationSum3(int k, int n, int startNumber, List<List<Integer>> result, List<Integer> current){
    if(k==0 && n==0){ result.add(new ArrayList<Integer>(current)); return;}
    if(k==0 || n<0) return;
    for(int i = startNumber ; i<=9 ; i++){
        if(i>n){
            break;
        }
        current.add(i);
        combinationSum3(k-1, n-i, i+1, result, current);
        current.remove(current.size()-1);
    }
}