Subsets (Power Set) ใน Python

สร้างทุก subset (power set) ของชุดตัวเลขที่กำหนด

ตัวอย่าง

Input: [1,2,3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

วิธีที่ 1: Backtracking (Recursive)

class Solution:
    def subsets(self, nums):
        res = []
        def backtrack(start, path):
            res.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i+1, path)
                path.pop()
        backtrack(0, [])
        return res

# ทดสอบ
sol = Solution()
print(sol.subsets([1,2,3,4]))

วิธีที่ 2: Bit Manipulation (Iterative)

def subsets_bit(nums):
    n = len(nums)
    res = []
    for mask in range(1 << n):  # 0 to 2^n - 1
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        res.append(subset)
    return res

print(subsets_bit([1,2,3]))

วิธีที่ 3: Iterative (Build up)

def subsets_iter(nums):
    res = [[]]
    for num in nums:
        res += [curr + [num] for curr in res]
    return res

print(subsets_iter([1,2,3]))

เปรียบเทียบ

สรุป

Iterative build (`res += [curr + [num] for curr in res]`) เขียนสั้น กระชับ เร็วที่สุดใน Python