描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

链接

216. 组合总和 III - 力扣（LeetCode） (leetcode-cn.com)

 

解法

 1 class Solution {
 2     List<List<Integer>> res = new ArrayList<>();
 3     Deque<Integer> path  = new ArrayDeque<>();
 4     public List<List<Integer>> combinationSum3(int k, int n) {
 5         backtracking(n, k, 1, 0);
 6         return res;
 7     }
 8 
 9     public void backtracking(int targetSum, int k, int StartIndex, int sum) {
10         if (sum > targetSum) { // 剪枝
11             return;
12         }
13         if (path.size() == k) {
14             if (sum == targetSum) {
15                 res.add(new ArrayList<>(path));
16             }
17             return;
18         }
19         for (int i = StartIndex; i <= 9 - (k - path.size()) + 1; i++) { // i <= 中的 等于不能忘记
20             sum += i;
21             path.add(i);
22             backtracking(targetSum, k, i + 1, sum);
23             sum -= i;
24             path.removeLast();
25         }
26     }
27 }

 

参考

carl