[Backtracking] Subset Sum

Subset Sum(부분 합 문제)

: 양의 정수들의 배열이 들어 올때, 배열의 부분합으로 일정 수를 만들 수 있으면 TRUE를, 만들 수 없으면 FALSE를 돌려준다.

Ex)

X = {8, 6, 7, 5, 3, 10, 9}

T = 15이면, {8,7}, {5,10}, {6,9}, {7,5,3} > TRUE

 

 

- Base Cases

T = 0 이면, 선택하지않으면 항상 TRUE 이다.

T < 0 이면, 항상 FALSE이다.

 

- General Case(점화식)

총합이 T인 부분집합에 대해, 해당 부분집합은 X의 원소 x에 대해 x를 포함하거나, 포함하지않거나의 두가지로 나뉜다.

1. x를 포함할 경우, T-x 인 X-{x}의 부분집합이 존재한다.

2. x를 포함하지 않을 경우, T 인 X-{x}의 부분집합이 존재한다.

즉, 문제Subset_sum(X, T)를 Subset_sum(X-{x}, T-x) 또는 Subset_sum(X-{x}, T)로 나눌 수 있다.

 

# 페슈도 코드
subsetsum(X, i, T):
	if T=0:
    	return TRUE
    elif T<0:
    	return FALSE
    else:
    	return subsetsum(X, i-1, T-X[i]) or subsetsum(X, i-1, T)

subsetsum_ recursion_ tree

 

 

Backtracking : General Pattern

백트래킹 알고리즘들은 일반적으로 결정들의 시퀀스를 만든다.

이는 특정 조건을 만족하는 재귀적인 구조를 만드는게 목적이고, 이것 자체가 대부분 시퀀스의 형태를 가진다.

▶ 결정의 연속이 시퀀스를 만들고 이 시퀀스는 결국 답을 만든다.

 

백트래킹으로 문제를 해결할 때...

각각의 재귀호출에서는 하나의 결정을 해야하고, 그 결정은 일관성이 있어야한다.

또한 각 재귀호출에서, 이전 결정에 대한 정보가 필요하다. 이 정보는 가능한 작은 형태로 넘겨져야한다.

* subsetsum에서도 이전 결정들에 따라, T-X[i] 또는 T를 넘겨준다.

backtracking은 재귀 무차별 대입으로 문제를 해결하는 방법.

 

 

 

 

---

https://jeffe.cs.illinois.edu/teaching/algorithms/

Algorithms by Jeff Erickson