组合总和Ⅲ

找出所有相加之和为 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-iii/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

剪枝递归回溯

结合 77. 组合 的回溯思路

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const res = [];
    const path = [];
    const maxLen = 9;
    // path 分支中的组合，start 搜索的起点
    const dfs = (start) => {
        const len = path.length;
        // 注意剪枝条件中 对应的 maxLen 为 k的最大可能数
        if (len + (maxLen - start + 1) < k || len > k) {
            return;
        }
        if (len === k && path.reduce((a, b) => a+b, 0) === n) {    //组合长度与k一致 且 组合中的和为n 时
            // 拷贝赋值，以免影响其他分支
            res.push([].concat(path));
            return;
        }
        path.push(start);
        dfs(start+1);   // 递归下一层
        path.pop(); // 回溯到上一步
        dfs(start+1);   // 递归下一层
    }
    if (k <= n) {
        dfs(1);
    }
    return res;
};

时间复杂度：O(C(n, k)*k)
空间复杂度：O(n)

剪枝递归回溯（优化版）

可参考 https://leetcode.cn/problems/combination-sum-iii/solution/hui-su-jian-zhi-by-liweiwei1419/
最终JS版的代码实现

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const res = [];
    const path = [];
    const dfs = (newK, sum, start) => {
        // [start, 9] 这个区间里的数都不够 k 个，剪枝
        if (10 - start < newK) {
            return;
        }
        if (newK === 0) {
            if (sum === n) {
                res.push([].concat(path));
            }
            return;
        }
        // 从示例1、2推断 i 最大可为 n - k + 1
        for (let i = start; i < Math.min(n - k + 2, 10); i++) {
            // 如果组合中数字之和 + 当前数字 大于 n，剪枝
            if (sum + i > n) {
                break;
            }
            path.push(i);
            dfs(newK - 1, sum + i, i + 1);
            path.pop();
        }
    }
    // K > n 则直接返回 []
    if (k <= 1 || k > 9 || n <= 0 || n > 60 || k > n) {
        return res;
    }
    // 由示例3，延申考虑，k=4，n为多少时开始无有效组合
    // n相对于k是有上限的：[9, 8, ... , (9 - k + 1)]，他们的和为 (19 - k) * k / 2，如果比这个数还大，除非组合中有10及以上的数字，否则 无法相加等于n
    if (n > (19 - k)*k/2) {
        return res;
    }
    dfs(k, 0, 1);
    return res;
};

位运算法

结合 77. 组合 中字典序法的思路，当组合中数字的二进制数中1的个数与k相同时，就符合 k个数的条件，可以将对应的 i 放入暂存的数组temp中，当暂存数组temp中数字之和为n 时，则 表示该temp组合 符合全部条件。

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const maxLen = 9;
    const res = [];
    const N = 1<<maxLen; // 即 512，所以其时间复杂度很高，性能不比回溯法好，但思路很奇巧
    for (let i = 1; i < N; i++) {
        if (i.toString(2).replace(/0/g, '').length !== k) {
            continue;
        } else {
            const temp = [];
            for (let j = 0; j < maxLen; j++) {
                if (i&(1<<j)) {    // i 与 1<<j 按位与运算
                    temp.push(j+1);
                }
            }
            // temp数字之和与n相等时，该组合符合条件
            if (temp.reduce((a,b) => a+b, 0) === n) {
                res.push([].concat(temp));
            }
        }
    }
    return res;
};