Vấn đề
Cần viết hàm JS nhận mảng số nguyên arr và số nguyên target. Với mỗi số, gán dấu '+' hoặc '-'. Tìm số cách gán dấu sao cho tổng bằng target.
Ví dụ:
const arr = [1, 1, 1, 1, 1]; const target = 3;
Kết quả:
const output = 5;
Giải thích:
5 cách: -1+1+1+1+1=3, +1-1+1+1+1=3, +1+1-1+1+1=3, +1+1+1-1+1=3, +1+1+1+1-1=3.
Ví dụ
Mã thực hiện:
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));
Kết quả
Kết quả in ra console:
5