SOS DP (Sum Over Subsets)

정의

SOS DP (Sum Over Subsets) 는 길이 2^N 의 배열 a 에 대해, 모든 mask (0..2^N-1) 마다 mask 의 부분 집합 (submask) 에 대한 합 을 O(N * 2^N) 에 구하는 DP 기법. “Sum Over Subsets” (부분 집합에 대한 합) 의 약자.

문제 상황과 동기

길이 2^N 배열 a, f[mask] = Σ_{submask ⊆ mask} a[submask].

• naive: 각 mask 마다 모든 submask 열거. O(3^N). N=20 이면 3^20 ~ 3.5 * 10^9, 불가.
• SOS DP: O(N * 2^N). N=20 이면 20 * 2^20 ~ 2 * 10^7, 1초 내 충분.

핵심 통찰: bit i 하나씩 추가하며, i 번째 bit 가 set 인 mask 의 DP 값을 i 번째 bit 가 없던 mask 의 값으로 보강. “각 bit 를 순서대로, 이미 고려한 bit 들은 자유롭게” 라는 divide-and-conquer 관점.

PS 에서: 포함-배제 DP (subset convolution), bitmask DP 고속화, Zeta/Mobius transform, graph 의 clique / independent set counting.

시각화

핵심 아이디어

상태 정의

dp[mask][i] = mask 의 부분 집합들 중, 하위 i 개 bit (bit 0 ~ i-1) 는 mask 와 정확히 일치하고 나머지 상위 bit 들은 mask 의 부분 집합인 집합에 대한 합.

점화식

dp[mask][0] = a[mask]
dp[mask][i] = dp[mask][i-1]
              (bit i-1 이 0 이면)
            | dp[mask][i-1] + dp[mask ^ (1<<(i-1))][i-1]
              (bit i-1 이 1 이면, i-1 번 bit 를 "자유" 로 만듦)

최종 f[mask] = dp[mask][N].

공간 최적화 (1D in-place)

i 차원 생략. i loop 안에서 mask loop 실행.

for i in 0..N-1:
    for mask in 0..(1<<N)-1:
        if mask & (1<<i):
            f[mask] += f[mask ^ (1<<i)]

이 때 f[mask] 는 i 단계에서 “하위 i 개 bit 자유, 나머지 고정” 의미. i=0 단계: bit 0 자유. i=1 단계: bits 0.1 자유 … i=N-1 단계: 모든 bit 자유 (부분 집합 합 완성).

Zeta / Mobius transform

SOS DP 의 덧셈 버전을 zeta transform (부분 집합 합), 그 역을 Mobius transform (차분 복원). subset convolution (서로소 부분 집합 쌍의 합 곱) 의 기초.

zeta:   f[mask] += f[mask ^ (1<<i)]    (SOS DP 와 동일)
mobius: f[mask] -= f[mask ^ (1<<i)]    (역연산, 음수 주의)

알고리즘

sos_dp(f, N):
    for i in 0..N-1:
        for mask in 0..(1<<N)-1:
            if mask & (1<<i):
                f[mask] += f[mask ^ (1<<i)]
    return f

구현

// SOS DP: O(N * 2^N) subset sum
// Input: N, then 2^N integers (array a)
// Output: f[mask] = sum of a[submask] for submask subseteq mask
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n; cin >> n;
  int sz = 1 << n;
  vector<long long> f(sz);
  for (auto& v : f) cin >> v;
  for (int i = 0; i < n; i++) {
      for (int mask = 0; mask < sz; mask++) {
          if (mask & (1 << i))
              f[mask] += f[mask ^ (1 << i)];
      }
  }
  for (auto& v : f) cout << v << ' ';
}

# SOS DP: O(N * 2^N) subset sum
n = int(input())
f = list(map(int, input().split()))
sz = 1 << n
for i in range(n):
  bit = 1 << i
  for mask in range(sz):
      if mask & bit:
          f[mask] += f[mask ^ bit]
print(*f)

3
1 2 3 4 5 6 7 8

1 3 4 10 6 14 16 36

복잡도

변형 / 활용

1. Subset Convolution

h[mask] = Σ_{sub ⊆ mask} f[sub] * g[mask ^ sub] (서로소 분할 곱). SOS DP + bit count 분리로 O(N^2 * 2^N).

2. Superset Sum (SOS over supersets)

모든 superset 에 대한 합. 반대 방향: for mask in 0..sz-1: if !(mask & (1<<i)): f[mask] += f[mask | (1<<i)].

3. Divisible / LCM subset counting

약수 관계를 bitmask 로 매핑해서 SOS DP 로 처리.

4. Graph 의 Independent Set Counting

bitmask 가 independent set 을 나타내도록 하여, superset DP 로 clique / independent set 개수.

함정

1. in-place 갱신 순서

mask 를 0..sz-1 순회. bit i 가 set 인 mask 만 갱신하므로, 작은 mask → 큰 mask 순서로 f[mask] 가 누적됨.

2. 오버플로우

a 값과 부분 집합 개수가 크면 64-bit 필요. C++ long long.

3. Mobius 음수

Mobius 변환은 f[mask] -= f[mask ^ (1<<i)]. mod 연산 시 양수 유지: f[mask] = (f[mask] - f[mask ^ bit] + MOD) % MOD.

4. N 제한

SOS DP 는 O(N * 2^N). N=25 (2^25=33M) 까지는 1초 내 가능. N=30 (2^30=1B) 은 불가.

BOJ 연습 문제

참고

• 비트마스크 DP
• 동적 계획법