77. Combinations
Tags:
Medium
Skills:
backtrack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
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
Time and space complexity
Solution
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};backtrack(start, path)