216. 组合总和 III

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

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

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

示例 1:

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

示例 2:

输入: 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
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

回溯-元素无重。

base case：找到了指定个数的数，且和为指定值，收集track中的值。

不可复选是从头开始找，但是用记忆数组去重。

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    List<Integer> track = new LinkedList<>();
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(1, 9, k, n, 0);
        return res;
    }

    void backtrack(int start, int end, int k, int target, int sum) {
        if (k == track.size()) {
            // 找到了指定个数的数，且和为指定值，收集track中的值
            if (sum == target) {
                res.add(new LinkedList<>(track));
            }
            return;
        }
        
        for (int i = start; i <= end; i++) {
            // 选择：索引入队，且累加和。
            track.addLast(i);
            sum += i;
            // start + 1，避免产生重复的子集。这是组合的特点，不是不可复选的特点。
            // 不可复选是从头开始找，但是用记忆数组去重。
            backtrack(i + 1, end, k, target, sum);
            // 撤销选择：索引出队，且和减少。
            sum -= i;
            track.removeLast();
        }
    }
}

• 时间复杂度： $O\left(\left(\begin{array}{c}M \\ k\end{array}\right) \times k\right)$ ，其中 $M$ 为集合的大小， 本题中 $M$ 固定为 9 。一共有 $\left(\begin{array}{c}M \\ k\end{array}\right)$ 个组合，每次递归中add的时间代价是 $O(k)$ 。
• 空间复杂度： $O(M)$ 。 track 数组的空间代价是 $O(k)$ ，递归栈空间的代价是 $O(M)$ ，故空间复杂度为 $O(M+k)=O(M)$。