การสร้างชุดตัวเลขที่ผลรวมเท่ากับเป้าหมาย (Combination Sum) ใน JavaScript

หาชุดตัวเลข m ตัวที่ผลรวมเท่ากับ n โดยใช้ตัวเลข 1-9 เท่านั้น และแต่ละชุดต้องไม่ซ้ำกัน (unique set)

ตัวอย่าง: m=3, n=4 → [[1,2,4]]; m=3, n=9 → [[1,2,6], [1,3,5], [2,3,4]]

ตัวอย่างโค้ด

const m = 3, n = 9;

const findSum = (m, n) => {
  const search = (from, prefix, m, n) => {
    if (m === 0 && n === 0) return res.push(prefix);
    if (from > 9) return;
    search(from + 1, prefix.concat(from), m - 1, n - from);
    search(from + 1, prefix, m, n);
  };
  const res = [];
  search(1, [], m, n);
  return res;
};

console.log(findSum(m, n));

ผลลัพธ์

ค่าที่แสดงในคอนโซลจะเป็นดังนี้:

[ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 2, 3, 4 ] ]