40. Combination Sum II
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 tìm tất cả các tổ hợp số trong mảng candidates sao cho tổng của các số trong tổ hợp bằng target. Các yêu cầu chính:
candidates chỉ được sử dụng một lần trong mỗi tổ hợp.candidates có thể trùng lặp, nhưng tổ hợp kết quả phải là duy nhất.Approach
Để giải bài toán này, ta có thể sử dụng kỹ thuật Backtracking kết hợp với việc sắp xếp mảng để loại bỏ các tổ hợp trùng lặp. Các bước chính:
candidates: Việc này giúp ta dễ dàng bỏ qua các phần tử trùng lặp khi duyệt.target và tiếp tục tìm kiếm với phần tử tiếp theo.candidates[i] == candidates[i-1]), ta bỏ qua để tránh tạo ra tổ hợp giống nhau.Time and space complexity
Solution
candidates đã được sắp xếp, các phần tử trùng lặp sẽ nằm liền kề nhau (ví dụ: [1, 1, 2,Điều kiện candidates[i] === candidates[i - 1]` giúp phát hiện các phần tử trùng lặp.i > index, điều đó có nghĩa là chúng ta đang duyệt qua một phần tử khác ở cùng cấp độ, và nếu phần tử này giống với phần tử trước đó (candidates[i] === candidates[i - 1]), thì chúng ta bỏ qua nó để tránh tạo ra tổ hợp trùng lặp.i === index, tức là đây là lần đầu tiên duyệt qua phần tử này ở nhánh hiện tại, chúng ta vẫn cần xét nó.1function combinationSum2(candidates: number[], target: number): number[][] {
2 let res: number[][] = [];
3 candidates.sort((a, b) => a - b)
4 function backtrack(path: number[], index: number, current_sum: 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 = index; i < candidates.length; i++) {
15 if (i > index && candidates[i] === candidates[i - 1]) {
16 continue;
17 }
18
19 path.push(candidates[i])
20 backtrack(path, i + 1, current_sum + candidates[i])
21 path.pop()
22 }
23 }
24
25 backtrack([], 0, 0)
26 return res;
27};