항상 DP 문제가 그렇듯 이 문제에도 중복되는(overlapping) 서브 문제들이 있습니다. 재귀 함수를 호출하다 보면 중복되는 부분집합들(subsets)을 여러번 시도해 보는 문제가 생깁니다. 이렇게되면 이 솔루션의 시간복잡도는 지수형태가 됩니다. 사실 이 문제는 NP-문제입니다. (다항형태의 시간복잡도를 가진 문제 솔루션이 없는 문제를 NP-문제라 합니다)
하지만 우리는 이 문제를 DP 를 이용해 가상-다항 시간(Pseudo-polynomial time)으로 풀어볼 수 있습니다. (가상-다항 시간이란, 입력값을 어느정도 제한하는 조건하에 다항시간안에 풀릴 수 있는 솔루션의 시간복잡도를 가상-다항 시간이라 말합니다.) 부울값을 가진 이차원 배열 $subset[][]$을 만들고 bottom up 방식으로 채우겠습니다. $subset[i][j]$ 의 값은 True 또는 False 가 될것입니다. 이 값의 의미는 $set[0\cdots j-1]$ 의 부분집합중 모든 합이 $i$ 와 같은 부분집합이 있다면 True 값이고 그렇지 않다면 False 를 가집니다. 최종적으로 우리는 $set[0\cdots n-1]$ 까지의 부분집합중 모든 합이 $i=sum$ 과 같은 부분집합이 존재하는지를 알고 싶기 때문에 $subset[sum][n]$ 을 찾으면 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# A Dynamic Programming solution for
# subset sum problem
# set[] 집합 안의 부분집합의 합이 sum 과 같으면
# True 를 반환한다.
def isSubsetSum(st, n, sm) :
# subset[i][j] 의 값은 set[0..j-1] 의 부분집합중 원소의
# 합이 i 와 같은 부분집합이 존재한다면 True 아니면 False
subset=[[False] * (sm+1) for _ in range(0, n+1)]
# sum 이 정확히 0 이 된다면 답은 True 입니다.
for i inrange(0, n+1) :
subset[i][0] = True
# sum 이 0 이 아니고 set 이 완벽히 비었다면
# (부분집합이 나올 여지가 없다면)
# 답은 False 가 됩니다.
for i inrange(1, sm +1) :
subset[0][i] = False
# 부분집합의 배열(테이블)을 bottom up 방식으로 채웁니다.
for i inrange(1, n+1) :
for j inrange(1, sm+1) :
if(j < st[i-1]) :
subset[i][j] = subset[i-1][j]
if (j >= st[i-1]) :
subset[i][j] = subset[i-1][j] or subset[i -1][j-st[i-1]]
