ปัญหา
รับอาร์เรย์ arr และ target แต่ละตัวเลขเลือกเครื่องหมาย + หรือ - จำนวนวิธีที่ผลรวมเท่ากับ target
ตัวอย่าง
const arr = [1, 1, 1, 1, 1]; const target = 3;
5 วิธี: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1 → 5
โค้ดตัวอย่าง (Memoization / DP)
const arr = [1, 1, 1, 1, 1]; const target = 3;
const waysToSum = (arr = [], target = 1) => {
const map = {};
const find = (arr, target, i) => {
let val = i + '->' + target;
if(map[val] !== undefined) return map[val];
if(i === 0){
if (target === 0 && arr[0] === 0) return 2;
return arr[0] === target || arr[0] === -target ? 1 : 0;
}
map[val] = find(arr, target + arr[i], i - 1) + find(arr, target - arr[i], i - 1);
return map[val];
};
return find(arr, target, arr.length-1);
};
console.log(waysToSum(arr, target));
ผลลัพธ์
5
