377. Combination Sum IV
Tags:
Medium
Skills:
backtrackDP
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 đếm số lượng các dãy số (có thứ tự) được tạo thành từ các phần tử trong mảng nums (có thể dùng lại nhiều lần), sao cho tổng của dãy số đó bằng target
Phân tích
[1][2][1] và [1][1][2] được coi là hai cách khác nhau.nums có thể dùng không giới hạn số lần Approach - bottom up DP
dp với dp[i] là số cách để tổng bằng idp = 1 (chỉ có 1 cách để tổng bằng 0, không chọn số nào)i từ 1 -> target , thử từng số num trong nums i >= num, cộng thêm dp[i - num] vào dp[i] (vì nếu đã có cách tạo ra i - num, thêm num vào cuối sẽ tạo ra tổng i).Time and space complexity
Solution - Bottom up DP
1function combinationSum4(nums: number[], target: number): number {
2 const dp: number[] = new Array(target + 1).fill(0)
3 dp[0] = 1;
4
5 for (let i = 1; i <= target; i++) {
6 for (const num of nums) {
7 if (i >= num) {
8 dp[i] = dp[i] + dp[i - num]
9 }
10 }
11 }
12
13 return dp[target];
14};1 if(i >= num) {
2 dp[i] = dp[i] + dp[i - num]
3 }Giải thích:
dp[i] là số cách để tạo tổng bằng i từ các số trong nums (có thể dùng lại)num , nếu i>=num , nghĩa là ta có thể thêm num vào một tổ hợp nào đó mà tổng của nó là i - num để tạo thành tổng mới là iVì sao cộng dp[i - num] vào dp[i]
i - num đều có thể thêm num vào cuối để thành tổng ii bằng cách dùng thêm số num chính là số cách tạo ra tổng i - num (tức là dp[i - num]) num trong numsVí dụ:
nums = [1,2][3], target = 4.i = 4, với num = 3, ta xét dp[4 - 3] = dp[1].Mỗi cách tạo ra tổng 1 đều có thể thêm số 3 vào cuối để thành tổng 4.
Tóm lại:
Câu lệnh này đảm bảo rằng mọi tổ hợp đạt tổng i đều được tính, bằng cách xây dựng từ các tổ hợp nhỏ hơn (i - num) và thêm số num vào cuối mỗi tổ hợp đó
Ảnh hưởng khi cho phép số âm
[1, -1] và target = 1, bạn có thể tạo ra vô số tổ hợp như [1], [1, -1, 1], [1, -1, 1, -1, 1], ... vì cứ thêm cặp -1, 1 vào là tổng không đổiCần thêm giới hạn gì để bài toán còn ý nghĩa?
Để tránh trường hợp tổ hợp vô hạn, cần bổ sung một trong các ràng buộc sau:
nums chỉ được dùng tối đa một lần (Giống như combination sum i/ii)x và x, thì sẽ luôn tạo ra vô hạn tổ hợp.Tóm tắt