组合III

找出所有相加之和为n的k个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

方法一：回溯

算法思路：

确定递归函数的返回值以及参数

除了n与k，我们还需要设置变量sum记录path中元素的和，startIndex记录循环搜索的起始位置
确定终止条件

当path大小达到k时终止递归，若此时path中的元素和为sum等于n，则在result中添加path
if(path.size() == k){
if(sum == n){
result.add(new ArrayList<>(path));
}
return;
}

单层搜索的过程

和77.组合一样，都是从startIndex开始遍历，其中sum来统计path中的元素之和，回溯后需要减回去。

for(int i = startIndex; i <= 9; i++){
            path.add(i);
            sum += i;
            backTracking(k, n, i + 1, sum);
            sum -= i;
            path.removeLast();
}

代码实现：

class Solution {
    public List<List<Integer>> result = new ArrayList<>();
    public LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1, 0);
        return result;
    }

    public void backTracking(int k, int n, int startIndex, int sum){
        if(path.size() == k){
            if(sum == n){
                result.add(new ArrayList<>(path));
            }
            return;
        }

        for(int i = startIndex; i <= 9; i++){
            path.add(i);
            sum += i;
            backTracking(k, n, i + 1, sum);
            sum -= i;
            path.removeLast();
        }
    }
}

方法二：剪枝优化

当元素总和已经大于n时，往后遍历就没有意义了，直接剪掉。

if(sum > n){
		return;
}

与77.组合一样，for循环也可以剪枝。

for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++)

参考

代码随想录 - 组合III

组合III

方法一：回溯

方法二： 剪枝优化

参考

方法二：剪枝优化