77. Combinations

Problem

Bài toán yêu cầu sinh ra tất cả các tổ hợp gồm k số khác nhau từ dãy số 1 → n, không quan trọng thứ tự trong tổ hợp. Đây là một bài toán điển hình về sinh tổ hợp, và giải pháp hiện quả nhất là sử dụng backtrack để duyệt tất cả các khả năng chọn k số từ n số

Approach

Sử dụng một hàm đệ quy, với mỗi bước ta quyết định chọn hoặc không chọn số hiện tại

Khi tổ hợp tạm thời đạt đủ k phần tử, ta thêm nó vào kết quả

Khi vượt quá n, dừng nhánh hiện tại

Để tránh trùng lặp, chỉ duyệt các số lớn hơn số vừa chọn ở bước trước

Time and space complexity

TC: O(C(n, k));

SC: O(C(n, k) * k), cần thêm O(k) cho call stack

Solution

typescripttypescript

1function combine(n: number, k: number): number[][] {
2    let res: number[][] = [];
3    function backtrack(idx: number, path: number[]): void {
4        if (path.length === k) {
5            res.push([...path]);
6            return;
7        }
8        for (let i = idx; i <= n; i++) {
9            path.push(i);
10            backtrack(i + 1, path)
11            path.pop()
12        }
13    }
14
15    backtrack(1, [])
16    return res;
17};

💡

Tóm tắt

backtrack(start, path)

Nếu path đủ k phần tử, copy vào kết quả

Duyệt i từ start → n:

Thêm i vào path

Gọi backtrack(i +1, path)

Xóa i khỏi path (backtrack)

Loading content...