✅ DFS ✅ 백트래킹

문제

링크

풀이

1. 문제 접근

수열의 모든 부분집합 중에서 원소의 합이 S가 되는 경우의 수를 구해야 하는데
그렇다면 모든 부분집합의 원소의 합을 모두 구해봐야 할까?
크기가 N개인 수열의 부분집합의 수는 2^N 개 인데 N의 최댓값이 20이니까 총 1048576 개이다.. 너무 많다..

그렇다면 가지치기를 통해 경우의 수를 줄여야 한다. -> 백트래킹

2. 문제 해결 로직 (풀이법)

백트래킹 (가지치기)의 기본 로직

어떤 노드의 유망성을 점검 후,
유망하지 않으면 배제시킨다. = 가지치기
해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. → 풀이시간 단축

• 부분집합들을 모두 뽑아서 더해볼 수는 없으니 백트래킹의 구현 알고리즘인 DFS (BFS도 가능하다고 알고 있으나 DFS로 풀이)
  즉 재귀를 사용하여 가지치기 조건에 걸린다면 곧바로 리턴하여 부모노드로 돌아가도록 하면 된다.
• 부분집합이라는건 각각의 원소를 포함할지 안할지에 대한 문제이다.
  따라서 가지치기에서의 "가지"는 원소를 차례대로 각각 더할지 안더할지로 나눠질 수 있다.
• 가지치기의 조건(유망성 판단)은 원소의 차례가 수열의 크기를 넘어서는 안된다는 것이다.

의사코드

int cnt = 0

void DFS(int sum, int idx){ // sum : 현재까지 더해진 총 값, idx : 더할 원소의 인덱스
	if(sum + arr[idx] == S) cnt ++
    if(idx == N) return;
    
    DFS(sum, idx+1) // 더하지 않고 다음 원소로 이동
    DFS(sum + arr[idx], idx+1) // 더하고 다음 원소로 이동
}

main(){
	cin >> N >> S
    for(i : 0 ~ N-1){
    	cin >> arr[i]
    }
    
    DFS(0,0) // 0번째 원소부터 더해감
    
    cout << cnt
}

3. 시간 복잡도 분석

$O(2^N)$

4. 문제에서 중요한 부분

• 부분집합이라는건 각각의 원소를 포함할지 안할지에 대한 문제이므로
  단순히 원소를 차례대로 이동하면서 더할지 안더할지로 가지를 나눠주면 되었다.

• 가지치기의 조건을 알기 어려웠다.
  처음에는 N의 값에 따라 가지를 쳐야하는게 아닌가 싶었지만 수열에 음수와 양수 모두 존재하므로 N의 값에 따라 가지치기를 할 수 없었고
  그렇다면 남아있는(?) 조건에 위배되는건 원소를 차례대로 각각 더하기 때문에 수열의 인덱스에서 벗어나면 안된다는 것이다.