LeetCode #78 Subsets: ขยายคำตอบ, backtracking หรือ bitmask เลือกแบบไหนดี

โจทย์ Subsets ให้คืนทุกชุดย่อยของ nums ที่สมาชิกไม่ซ้ำกัน ถ้ามี n ตัว คำตอบมี 2^n ชุดอยู่แล้ว ดังนั้นเวลาและพื้นที่ผลลัพธ์ต่ำกว่า O(n·2^n) ไม่ได้ เพราะต้องคัดลอกสมาชิกลงแต่ละชุด

วิธี 1: ขยายคำตอบทีละสมาชิก

เริ่มจาก [[]] เมื่อเจอค่าใหม่ ให้นำค่านั้นต่อท้ายทุกชุดที่มีอยู่ อ่านง่ายและเป็น default ที่ดีสำหรับโจทย์นี้

วิธี 2: Backtracking

เลือกว่าจะเพิ่มสมาชิกถัดไปหรือไม่ แล้ว copy path ตอนเก็บคำตอบ เหมาะเมื่อโจทย์ต่อยอดเป็น pruning ตามเงื่อนไข เพราะแทรก guard ใน recursion ได้ตรงจุด

วิธี 3: Bitmask

เลข 0..2^n-1 แทนคำตอบหนึ่งชุด โดย bit ที่ i บอกว่าเลือก nums[i] หรือไม่ ลำดับแน่นอนและแบ่งช่วง mask ให้ worker ได้ แต่ intent อ่านยากกว่าสองวิธีแรก

from __future__ import annotations

import unittest


def subsets_iterative(nums: list[int]) -> list[list[int]]:
    result = [[]]
    for value in nums:
        result += [subset + [value] for subset in result]
    return result


def subsets_backtracking(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []

    def visit(start: int, path: list[int]) -> None:
        result.append(path.copy())
        for index in range(start, len(nums)):
            path.append(nums[index])
            visit(index + 1, path)
            path.pop()

    visit(0, [])
    return result


def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    return [
        [value for index, value in enumerate(nums) if mask & (1 << index)]
        for mask in range(1 << len(nums))
    ]


def canonical(groups: list[list[int]]) -> set[tuple[int, ...]]:
    return {tuple(group) for group in groups}


class SubsetsTests(unittest.TestCase):
    def test_all_methods(self):
        expected = {(), (1,), (2,), (1, 2)}
        for solve in (subsets_iterative, subsets_backtracking, subsets_bitmask):
            self.assertEqual(canonical(solve([1, 2])), expected)
            self.assertEqual(solve([]), [[]])


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	ขยายทีละสมาชิก	Backtracking	Bitmask
อ่านง่าย	ดีที่สุด	ดี	ปานกลาง
เพิ่ม pruning	ไม่ถนัด	ดีที่สุด	ไม่ถนัด
แบ่งช่วงงาน	ปานกลาง	ปานกลาง	ดีที่สุด
ใช้ memory นอกผลลัพธ์	O(2^n) ระหว่างขยาย	O(n) stack/path	O(n) ต่อ mask
ต้อง sort input	ไม่ต้อง	ไม่ต้อง	ไม่ต้อง
streaming	ทำได้เป็นรอบ	yield ได้ง่าย	yield ทีละ mask

ทุกวิธีใช้เวลา O(n·2^n) และผลลัพธ์กินพื้นที่ O(n·2^n) เลือก iterative เป็น default, backtracking เมื่อมี constraint และ bitmask เมื่อเลข mask มีประโยชน์ต่อระบบรอบข้าง

Recap

• จำ lower bound จากขนาดคำตอบ 2^n
• copy path ก่อนเก็บใน backtracking
• เทสต์ input ว่างซึ่งต้องได้ [[]]
• ระบุเรื่องลำดับคำตอบถ้าผู้เรียกพึ่งพา