การหา Subset ทั้งหมด (Power Set) ของอาร์เรย์ใน JavaScript

บทความนี้สาธิตการสร้าง power set (ทุก subset ที่เป็นไปได้) ของอาร์เรย์

ตัวอย่าง

input: [1, 2, 3]
output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

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

const arr = [1, 2, 3];

const findAllSubsets = (arr = []) => {
  arr.sort();
  const res = [[]];
  let count, subRes, preLength;
  for (let i = 0; i < arr.length; i++) {
    count = 1;
    while (arr[i + 1] && arr[i + 1] == arr[i]) {
      count += 1;
      i++;
    }
    preLength = res.length;
    for (let j = 0; j < preLength; j++) {
      subRes = res[j].slice();
      for (let x = 1; x <= count; x++) {
        if (x > 0) subRes.push(arr[i]);
        res.push(subRes.slice());
      }
    }
  }
  return res;
};

console.log(findAllSubsets(arr));

ผลลัพธ์

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

คำอธิบาย

Iterative approach: เริ่มจาก [[]] สำหรับแต่ละ unique element (จัดการ duplicate ด้วย count) นำ subset ที่มีอยู่ clone และเพิ่ม element นั้น 1 ถึง count ครั้ง

จัดการ duplicate โดยนับ count ติดกัน (ต้อง sort ก่อน)

Time: O(n * 2^n), Space: O(n * 2^n)