输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

输入：n = 1, k = 1
输出：[[1]]

function combine(n: number, k: number): number[][] {
    const res: number[][] = []
    const dfs = (depth: number, preNums: number[]) => {
        if(depth === k){
            res.push([...preNums])
            return
        }
        // 保证组合里的数字是「升序排列」的，就永远不会出现 [2,1] 这种逆序的重复组合！
        // 有数字选比最后一个大的，没数字从1开始选
        const start = preNums.length > 0 ? preNums[preNums.length - 1] + 1 : 1
        // 让之后选择的数字都比之前的大
        // for(let num = start; num <= n; num++){ 按这个写法会选到太大的数字导致无效遍历
        // 选择的数字最大就是n - (k - depth)
        for(let num = start; num <= n - (k - depth) + 1; num++){
            dfs(depth + 1, [...preNums, num])
        }
    }
    dfs(0, [])
    return res
};