216. 组合总和 III

https://leetcode-cn.com/problems/combination-sum-iii/

解法一：回溯

经典回溯，js和py不同，因此没法用回溯总结中的简化格式。每层从start+1开始向后dfs搜索，第1层从0开始，设置两个递归出口，tmp长度超过k，或者tmp之和超过n。思路很直观，缺点是没有剪枝，速度较慢（180ms）

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const ret = []
    
    const backtrack = (tmpList, start, sum) => {
        if (tmpList.length > k) return
        if (sum > n) return
        if (sum === n && tmpList.length === k) {
            ret.push(Array.from(tmpList))
            return
        }
        for (let i = start + 1; i < 10; i++) {
            tmpList.push(i)
            backtrack(tmpList, i, sum+i)
            tmpList.pop()
        }
    }

    backtrack([], 0, 0)
    return ret
};

优化：剪枝，省略不必要的搜索，因为搜索范围是递增的，只要当前组合总和大于n，则不用再往后搜索了。56ms，beat100%

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const ret = []
    //回溯函数，tmp记录当前组合元素，start为本层搜索起点，sum为总和
    const backtrack = (tmpList, start, sum) => {    
        if (tmpList.length > k) return
        if (sum === n && tmpList.length === k) {
            ret.push(Array.from(tmpList))
            return
        }
        for (let i = start + 1; i < 10; i++) {  // 从start+1向后搜索
            if (sum + i > n) break  //总和超过n，则后面的元素都不用再遍历了（必然也超
            tmpList.push(i)
            backtrack(tmpList, i, sum+i)
            tmpList.pop()
        }
    }

    backtrack([], 0, 0)
    return ret
};