77. 组合【中等】

题目链接

const backTracking = (n: number, k: number, start:number, newRes: number[], result: number[][] ) => {
    if (newRes.length === k) { // 易错
        const item = [...newRes];
        result.push(item);
        return;
    }
    for(let i = start; i<=n ; i++) {
        newRes.push(i);
        backTracking(n, k, i+1, newRes, result);
        newRes.pop();
    }
};

function combine(n: number, k: number): number[][] {
    const result: number[][] = [];
    backTracking(n, k, 1, [], result);
    return result;
};

剪支版：

const backTracking = (n: number, k: number, start:number, newRes: number[], result: number[][] ) => {
    if (newRes.length === k) {
        const item = [...newRes];
        result.push(item);
        return;
    }
    for(let i = start; i<=n-(k-newRes.length)+1 ; i++) {
        newRes.push(i);
        backTracking(n, k, i+1, newRes, result);
        newRes.pop();
    }
};

function combine(n: number, k: number): number[][] {
    const result: number[][] = [];
    backTracking(n, k, 1, [], result);
    return result;
};