[C++] Boj 1182 부분수열의 합

문제 링크

1182 부분수열의 합

 

접근

모든 경우의 수를 확인하는 백트래킹 문제이다. N개의 정수로 이루어진 수열이 있을 때, 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성해야 한다.

 

이때, 중요한 점은 크기가 양수인 부분 수열 중에서 경우의 수를 구해야 한다는 것이다. 이 말은, 공집합은 포함하지 않는다는 말이다. 

 

이 문제는 중학교 때 배웠던 부분 집합 구하기 경우의 수 문제를 떠올려 쉽게 해결할 수 있다.

만약 n1, n2, n3의 수 중 부분 수열을 만들어 합 S를 만들어야 한다면, n1을 선택하고, 안 하고, n2를 선택하고, 안 하고를 반복해서 선택한 숫자들의 합이 S가 되게 만들면 된다.

 

이때 주의해야 할 점은 S가 1 이상인 경우는 상관없으나 S가 0일 때 아무것도 선택하지 않을 수 있다. 그것이 바로 공집합이고, 따라서 마지막에 예외 처리를 해 주어야 한다. 

 

코드

#include<iostream>
#include <vector>
using namespace std;

int N, S;
int cnt;

// 접근
// 숫자들 중에 특정 수를 더할 것인지, 안 더할 것인지 여부를 판단하여 진행한다. 

// int: 정수
// bool: 그 정수를 방문 했는지
vector<pair<int, bool>> numbers;

// numberConut: 몇 번째 숫자까지 순회했는지
// numbersSum: 현재 고른 수 들의 합
void Solve(int numberConut, int numbersSum)
{
    if (N == numberConut)
    {
        if (S == numbersSum) cnt++;
        return;
    }

    Solve(numberConut + 1, numbersSum + numbers[numberConut].first);
    Solve(numberConut + 1, numbersSum);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> S;


    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        numbers.push_back({ tmp, false });
    }

    Solve(0, 0);
    // 합이 0일 때 아무것도 선택하지 않을 수 있으므로 그걸 제외시킨다.
    if (S == 0) cnt--;
    cout << cnt;

    return 0;
}