ปัญหา
กำหนดอาร์เรย์ unique integers และ target นับจำนวน combination (ลำดับสำคัญ, 允许重复) ที่รวมได้ target
ตัวอย่าง
arr = [1,2,3], target = 4 combinations: (1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2), (3,1) -> 7
ตัวอย่างโค้ด
const arr = [1, 2, 3];
const target = 4;
const sumUpto = (nums = [], target = 1, map = {}) => {
if (target === 0) {
return 1;
}
if (typeof map[target] != "undefined") {
return map[target];
}
let res = 0;
for (let i = 0; i < nums.length; i++) {
if (target >= nums[i]) {
res += sumUpto(nums, target - nums[i], map);
}
}
map[target] = res;
return res;
};
console.log(sumUpto(arr, target));
ผลลัพธ์
7
คำอธิบาย
DP with memoization: f(target) = sum f(target - nums[i]) สำหรับทุก i
Base case: target = 0 -> 1 way (empty combination)
นับ permutation (ลำดับสำคัญ) ไม่ใช่ combination
Time: O(target * n) ด้วย memoization
