39. Combination Sum
Tags:
Medium
Skills:
backtrack
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Approach
current_sum) = target, thêm tổ hợp hiện tại vào kết quảtarget, dừng việc duyệt nhánh đóTime and space complexity
Solution - backtracking
1function combinationSum(candidates: number[], target: number): number[][] {
2 const res: number[][] = []
3
4 function backtrack(path: number[], current_sum: number, start_index: number): void {
5 if (current_sum === target) {
6 res.push([...path])
7 return;
8 }
9
10 if (current_sum > target) {
11 return;
12 }
13
14 for (let i = start_index; i < candidates.length; i++) {
15 path.push(candidates[i]);
16 backtrack(path, current_sum + candidates[i], i);
17 path.pop();
18 }
19 }
20
21 backtrack([], 0, 0);
22 return res;
23};