[BOJ] C++ 1182 부분수열의 합 - 백트래킹 구현하기

1182번: 부분수열의 합

예제

5 0
-7 -3 -2 5 8

ans : 1

---

백트래킹에 익숙하지 않은 분들은

[알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제

이 글을 꼭 먼저 읽어보시기 바랍니다.

---

N개의 정수의 부분 합을 모두 구해야 한다. N과 M 문제와 상당히 비슷한 냄새를 풍긴다. 전형적인 백트래킹 문제이므로 비슷하게 트리를 짜보자. 빈 리스트를 시작으로 수를 넣을지 말지 계산해서 트리를 짜면 된다. 트리의 왼쪽 자식은 해당 순번의 숫자를 넣지 않는 경우이다. 따라서 가장 왼쪽 아래의 자식은 아무것도 넣지 않은 공집합이지만 편의상 0으로 기록했다.

이런 트리를 만들게끔 구현하면 된다.

 

• base condition : n개의 수를 모두 더할지 말지 정하면 종료, cur == n
• 함수 형태 : void func(int cur, int sum) : cur 번째 수를 더할지 말지 정하고 부분합 구한 결과를 sum으로 계산
• 재귀식 : func(cur+1, sum) : cur 번째 수 더하지 않음, func(cur+1, sum + arr [cur]) : cur 번째 수 더함.

이를 바탕으로 구현해보자. 주의할 점은 S 값이 0이면 트리상 공집합을 0으로 표기했기에 하나 빼줘야 한다.

/** 백트래킹 1182 부분수열의 합 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 22
using namespace std;

int arr[MAX];
int N, S, res = 0;

void func(int cur, int sum)
{
    if (cur == N)
    {
        // base condition
        if (sum == S)
            res++;
        return;
    }
    func(cur + 1, sum);
    func(cur + 1, sum + arr[cur]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> S;
    for (int i = 0; i < N; i++)
        cin >> arr[i];

    func(0, 0);
    if (S == 0)
        res--;
    cout << res;
}