[알고리즘]백트래킹-sum of subset

Sum of subset Sum of subset 문제에 대해 정의하면 아래와 같습니다. 1부터 N까지 숫자를 조합했을때 , 합이 K가 되는것을 찾는 문제 입니다. 우리가 해결해야 할 문제는 N이 4이고 K가 5라고 합시다. 이때, 가능한 조합은 {①,④},{②,③}이 될 것입니다. 해당 문제를 bruteforce와 backtracking 방식으로 접근해보겠습니다. Brute force 방식 각 숫자마다 뽑는경우와, 뽑지 않는경우 2가지 상태가 존재합니다. 따라서 시간복잡도는 N개의 숫자가 있는경우 O(2N)이라고 할 수 있습니다. 아래는 N이 4일때의 예시 입니다. 백트래킹 방식 물론 Brute Force의 경우에도 가능한 모든 경우를 탐색하므로, 문제가 풀립니다. 하지만 필요없는 탐색을 하는 경우가 있습니다. 유망 함수는 아래와 같이 정의할수 있습니다. 첫째, 이미 현재 조합으로 합이 K가 된경우가 있습니다. 이럴경우 더이상 탐색하지 않아도 됩니다. 둘째, 해당 숫자를 추가했을때...

원문링크 : [알고리즘]백트래킹-sum of subset