Subset Sum: 부분집합 합

정의

집합 $\{a_1,\dots ,a_n\}$ 에서 부분집합의 합이 정확히 T가 되는 부분집합이 존재하는가를 묻는 결정 문제.

• 일반 경우: NP-complete (다항 시간 알고리즘 미발견)
• 원소 값이 작거나 T가 작으면: 의사 다항 시간 DP O(N x T)
• N <= 40이면: Meet-in-the-Middle O(2^(N/2) x N)

문제 상황

배열 원소들의 부분집합 중 합이 T인 것이 있는가?

naive (브루트포스): 2^N개 부분집합 모두 확인. N=20이면 ~1M, N=40이면 ~1조로 불가능.

핵심 통찰: dp[s]를 “합이 s인 부분집합 존재 여부”로 정의하고, 각 원소를 순서대로 처리. dp 테이블의 크기는 T+1이므로 T가 작으면 효율적.

시각화

DP 갱신 과정 (원소 {2, 3, 4}, T=7)

flowchart LR
    A["초기: 합 0만 달성 가능"]
    B["원소 2 처리: 합 0, 2 달성 가능"]
    C["원소 3 처리: 합 0, 2, 3, 5 달성 가능"]
    D["원소 4 처리: 합 0, 2, 3, 4, 5, 6, 7 달성 가능"]
    A -->|"역순 갱신 적용"| B
    B -->|"역순 갱신 적용"| C
    C -->|"역순 갱신 적용"| D

Meet-in-the-Middle 흐름 (N=40)

flowchart TD
    In["원소 배열 N개 입력"]
    L["왼쪽 N/2개의 모든 부분집합 합 열거"]
    R["오른쪽 N/2개의 모든 부분집합 합 열거"]
    Srt["왼쪽 합 목록 정렬"]
    Qry["오른쪽 각 합 s 에 대해 T-s 이분탐색"]
    Out["T-s 존재 시 YES 출력"]
    In -->|"절반 분할"| L
    In -->|"절반 분할"| R
    L --> Srt
    R --> Qry
    Srt --> Qry
    Qry --> Out

핵심 아이디어

DP O(N x T)

상태: dp[s] = 합이 s인 부분집합 존재 여부 (boolean).

초기: dp[0] = true, 나머지 false.

전이: 각 원소 x에 대해, x를 포함할 수 있으면 dp 갱신.

역순 갱신 (s를 T에서 x까지 감소): 동일 원소의 중복 사용 방지. 순방향 갱신 시 한 원소를 여러 번 사용 가능한 Unbounded Knapsack이 됨.

Meet-in-the-Middle O(2^(N/2) x N)

T가 너무 크거나 원소가 실수일 때 DP 적용 불가능. N <= 40 조건에서 사용:

1. 배열을 절반으로 분할: L = a[0..n/2-1], R = a[n/2..n-1]
2. 각 절반의 모든 2^(n/2)개 부분집합 합 열거
3. 왼쪽 합 목록 정렬 후, 오른쪽 각 합 s에 대해 T-s를 이분탐색

알고리즘

# DP O(N*T)
dp[0] = true, dp[1..T] = false

for each x in a:
    for s = T downto x:       # 역순: x를 1번만 사용
        dp[s] = dp[s] OR dp[s - x]

return dp[T]

# Meet-in-the-Middle O(2^(N/2)*N)
L = a[0..n/2-1],  R = a[n/2..n-1]

SumL = [subset sum of L for each 2^(n/2) subsets]
SumR = [subset sum of R for each 2^(n/2) subsets]
sort(SumL)

for s in SumR:
    if binary_search(SumL, T - s):
        return true
return false

구현

#include <bits/stdc++.h>
using namespace std;
​
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
​
  int n, T;
  cin >> n >> T;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
​
  vector<bool> dp(T + 1, false);
  dp[0] = true;
​
  for (int x : a) {
      for (int s = T; s >= x; s--) {  // 역순 갱신: 중복 사용 방지
          if (dp[s - x]) dp[s] = true;
      }
  }
​
  cout << (dp[T] ? "YES" : "NO") << "\n";
  return 0;
}

import sys
input = sys.stdin.readline
​
def solve():
  n, T = map(int, input().split())
  a = list(map(int, input().split()))
​
  dp = [False] * (T + 1)
  dp[0] = True
​
  for x in a:
      for s in range(T, x - 1, -1):  # 역순 갱신
          if dp[s - x]:
              dp[s] = True
​
  print("YES" if dp[T] else "NO")
​
solve()

4 9
1 2 3 5

YES

3 10
2 3 4

NO

1 5
5

YES

복잡도

함정

1. 역순 vs 순방향 갱신

역순 갱신(s = T downto x)을 빠뜨리고 순방향으로 갱신하면 동일 원소를 여러 번 사용하는 Unbounded Knapsack이 됩니다.

// 잘못된 예 (같은 원소 중복 사용)
for (int s = x; s <= T; s++)
    if (dp[s - x]) dp[s] = true;

// 올바른 예 (0-1, 각 원소 최대 1번)
for (int s = T; s >= x; s--)
    if (dp[s - x]) dp[s] = true;

2. dp[0] 초기화 누락

합이 0인 공집합은 항상 존재. dp[0] = true 없이 시작하면 아무것도 true가 되지 않음.

3. T 초과 원소 스킵 누락

원소 x > T이면 어떤 부분집합에 넣어도 합이 T를 초과. if (x > T) continue로 스킵.

4. 음수 원소

원소에 음수가 있으면 인덱스가 음수가 되어 배열 접근 오류. 오프셋 처리 또는 다른 접근 필요.

5. Meet-in-the-Middle 에서 개수 세기

T-s를 이분탐색으로 존재 여부만 확인하면 되지만, 합이 T인 부분집합의 개수를 세려면 이분탐색 upper_bound - lower_bound 차이 활용.

BOJ 연습 문제

참고

• Knapsack (value 있는 확장, 0-1 배낭)
• DP Bitfield
• SOS DP