Kiểm tra tổ hợp có thể cộng thành mục tiêu trong JavaScript

Mô tả vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng các số nguyên duy nhất arr làm đối số đầu tiên, và tổng mục tiêu làm đối số thứ hai.

Hàm phải đếm số lượng tất cả các cặp (cho phép lặp lại) có thể cộng thành tổng mục tiêu và trả về số lượng đó.

Ví dụ, nếu đầu vào là:

const arr = [1, 2, 3]; 
const target = 4;

Thì đầu ra nên là:

const output = 7;

Giải thích đầu ra

Vì các cách tổ hợp có thể là:

(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

Ví dụ minh họa

Mã thực hiện (sử dụng đệ quy có memoization):

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));

Đầu ra

Kết quả trong console sẽ là:

7