[Algorithm]Baekjoon 1182번 : 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
 
using namespace std;
 
 
int answer = 0;
int target = 0;
int maxSize = 0;
 
void solution(int index, int sum, vector<int>& numbers)
{
    int before = sum;
    sum += numbers[index];
 
    if (sum == target) answer++;
 
    if (index+1 <= maxSize - 1)
    {
        solution(index+1, before, numbers);
        solution(index+1, sum, numbers);
    }
    else return;
}
 
 
int main()
{
    int n = 0;
    int s = 0;
    int input = 0;
    vector<int> numbers;
    
    cin >> n >> s;
 
    target = s;
    maxSize = n;
    for (int i = 0; i < n; i++)
    {
        cin >> input;
        numbers.push_back(input);
    }
 
    solution(0, 0, numbers);
 
    // N은 1이상 20이하
    // S는 절대값 1000,000 이하.
 
    cout << answer;
}
 

 

백트래킹 기본예제 중 하나인 부분수열의 합 문제다.

백트래킹은 완전탐색을 할 때, 조건에 따라 더이상 탐색을 진행하지않고 다시 되돌아가는 것을 의미한다.

그렇기 때문에 되돌아가는 조건을 잘 설정하는게 관건이고 성능에 큰 영향을 미칠것이다.