Подмножества и множество всех подмножеств

Подмножества и булеан

# A set of n elements → 2^n subsets
for n in range(5):
    print(f'n={n}: {2**n} subsets')
# n=0: 1  (just the empty set)
# n=1: 2  ([], [x])
# n=2: 4  ([], [a], [b], [a,b])
# n=3: 8  (as enumerated above)
# n=4: 16

Генерация подмножеств с помощью поиска с возвратом

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(list(path))   # every state is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])    # CHOOSE
            backtrack(i + 1, path)  # EXPLORE (advance start)
            path.pop()              # UNCHOOSE
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Подход с битовой маской

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

print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differ

Итеративная генерация подмножеств

def subsets_iterative(nums):
    result = [[]]  # start with empty set
    for num in nums:
        # For each existing subset, create a new subset with num added
        result += [subset + [num] for subset in result]
    return result

print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Подмножества II: обработка дубликатов

def subsets_with_dups(nums):
    nums.sort()  # sort to group duplicates together
    result = []
    def backtrack(start, path):
        result.append(list(path))
        for i in range(start, len(nums)):
            # Skip duplicates at the same tree level
            if i > start and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]]  — no duplicate subsets

Почему пропуск дубликатов работает

# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once

nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)

def subsets(nums):
    result = []
    def bt(start, path):
        result.append(list(path))
        for i in range(start, len(nums)):
            path.append(nums[i]); bt(i+1, path); path.pop()
    bt(0, [])
    return result

def subsets_with_dups(nums):
    result = []
    def bt(start, path):
        result.append(list(path))
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]: continue
            path.append(nums[i]); bt(i+1, path); path.pop()
    bt(0, [])
    return result

print(len(subsets_with_dups([1,2,2])), 'unique subsets')  # 6

Подмножества фиксированного размера (сочетания размера k)

def combine(n, k):
    result = []
    def backtrack(start, path):
        if len(path) == k:
            result.append(list(path))
            return
        # Prune: need (k - len(path)) more elements from [start..n]
        # At most (n - start + 1) elements remain
        if n - start + 1 < k - len(path):
            return  # not enough elements left
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return result

print(combine(4, 2))  # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3)))  # C(10,3) = 120

Применение степенного множества

def max_subset_sum(nums, k):
    '''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
    # Backtracking approach: enumerate all k-subsets
    max_s = [float('-inf')]
    def bt(start, path, curr_sum):
        if len(path) == k:
            max_s[0] = max(max_s[0], curr_sum)
            return
        remaining_spots = k - len(path)
        for i in range(start, len(nums)):
            if len(nums) - i < remaining_spots: break  # prune
            bt(i+1, path+[nums[i]], curr_sum+nums[i])
    bt(0, [], 0)
    return max_s[0]

# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
    return sum(sorted(nums, reverse=True)[:k])

nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3))       # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3))  # 20

Проверка суммы подмножества

# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
    def bt(start, remaining):
        if remaining == 0: return True
        if remaining < 0 or start == len(nums): return False
        # Include nums[start]
        if bt(start + 1, remaining - nums[start]): return True
        # Exclude nums[start]
        return bt(start + 1, remaining)
    return bt(0, target)

# DP version: O(n * target) time
def subset_sum_dp(nums, target):
    dp = {0}
    for num in nums:
        dp |= {s + num for s in dp}
    return target in dp

print(subset_sum_bt([3, 1, 4, 1, 5], 6))  # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6))  # True

Сложность перечисления подмножеств

import time

def count_subsets(n):
    nums = list(range(n))
    result = []
    def bt(start, path):
        result.append(None)  # count without storing
        for i in range(start, len(nums)):
            path.append(i); bt(i+1, path); path.pop()
    bt(0, [])
    return len(result)

for n in [10, 15, 20]:
    start = time.time()
    cnt = count_subsets(n)
    elapsed = time.time() - start
    print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')

Сравнение всех трёх подходов

# All three approaches for [1,2,3]
nums = [1, 2, 3]

# 1. Backtracking
def bt(start, path, res):
    res.append(list(path))
    for i in range(start, len(nums)):
        path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)

# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
        for mask in range(1<<len(nums))]

# 3. Iterative
res3 = [[]]
for num in nums:
    res3 += [s+[num] for s in res3]

print('All produce', len(nums)**2, '-ish subsets:',
      len(res1), len(res2), len(res3))  # all 8

Проверка знаний

Итоги урока