Cặp subarray có tổng bằng nhau trong JavaScript

Viết hàm kiểm tra có thể chia mảng thành 2 subarray không giao nhau, bao phủ toàn bộ mảng, mà tổng hai subarray bằng nhau không.

Ví dụ: [5,3,7,4,1,8,2,6] → true ([5,3,4,6] và [7,1,8,2] đều sum=18).

Ví dụ

const arr = [5, 3, 7, 4, 1, 8, 2, 6];
const canPartition = (arr = []) => {
  const sum = arr.reduce((acc, val) => acc + val);
  if (sum % 2 !== 0) return false;
  const target = sum / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of arr) {
    if (dp[target - num]) return true;
    for (let i = target; i >= num; i--) dp[i] = dp[i - num];
  }
  return false;
};
console.log(canPartition(arr));

Kết quả

true