August 16, 2021 https://www.youtube.com/watch?v=SSSTVXj_JNk

A의 부분집합의 합이 15가 되는 경우의 수 - 예시: {8,7} {5,10} {7,5,3} {6,9}

어떤 부분집합을 만들었는데 안됨 → Backtrack 해서 다른 케이스 시도 (반복)

subsetSum2(A, i, S): #{A[0], ... , A[i]} -> 합이 S가 되는 subset (true/false)
	if S===0: return true
	else 

이렇게 유추해봤을때 해는 총 4개가 나오고,

n-Queens 문제 처럼 한가지 경우 아래 모든 경우를 다 해보고 반복한다

1 또는 0으로 경우를 가정하고 하나씩 더해서 current-sum을 만든다

이런 경우의 수 들 중에서 current-sum이 S면 x를 출력한다

배열이 오름차순으로 정렬되어 있으면 알아봐야 할 경우의 수가 줄어든다.