[알고리즘] 백트래킹, 완전 탐색 (1182 부분수열의 합 - C++)

백준 1182번 소스코드

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm> 

using namespace std;

int result = 0;
int S, N;
int arr[20];

void backtracking(int idx, int sum){
	sum = sum+arr[idx];
	if (idx >= N) return;
	
	if (sum == S) result++;
	
	backtracking(idx+1, sum);
	backtracking(idx+1, sum-arr[idx]);
} 
int main(void){
	cin >> N >> S;
	for(int i=0; i<N; i++){
		cin >> arr[i];
	}	
	backtracking(0, 0);
	cout << result;
}

 

백트래킹 부분만 따로 살펴보면,

void backtracking(int idx, int sum){
	sum = sum+arr[idx]; //일단 sum에 더해둔다.
	if (idx >= N) return; //N이 넘을 경우 return하여 함수 종료
	
	if (sum == S) result++; //sum이 S와 같을 경우 result에 1 더하기
	
    //다음 index로 넘어가기
	backtracking(idx+1, sum); //이번 횟수의 수를 더했을 때
	backtracking(idx+1, sum-arr[idx]); //이번 횟수의 수를 더하지 않았을 때
}