Leetcode - Combination Sum III

[分析] 思路就是枚举k个数所有可能的组合并判断是否符合条件。递归时需要如下状态量：k——还可以添加多少个数字 ，gap——和目标之前的差距, base——本次递归可使用的最小数，item——正在构造的一个解，result——全部解。

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        recur(k, n, 1, new ArrayList<Integer>(), result);
        return result;
    }
    public void recur(int k, int gap, int base, ArrayList<Integer> item, List<List<Integer>> result) {
        if (k == 0 && gap == 0) {
            result.add((ArrayList<Integer>)item.clone());
            return;
        }
        if (k == 0 || gap < 0) return;
        for (int i = base; i <= 9 && i <= gap; i++) {
            item.add(i);
            recur(k - 1, gap - i, i + 1, item, result);
            item.remove(item.size() - 1);
        }
    }
}