[백준/C++] 1182: 부분수열의 합

출처 - https://www.acmicpc.net/problem/1182

정보

• 이름: 부분수열의 합
• 난이도: Silver 2
• 알고리즘
  • 브루트포스 알고리즘
  • 백트래킹

 

해설

우선 수열이 될 배열에 입력 값들을 저장합니다.

 

그 후, 배열을 앞에서부터 순회하며 부분 수열을 만듭니다. 부분 수열의 합이 S와 같다면 cnt를 1 증가시킵니다.

 

문제에서 공집합을 제외(크기가 양수인 부분수열)하라고 하니 공집합의 합인 S == 0 인 경우 cnt를 1 감소시킵니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, s, cnt;
int nums[25];
int isUsed[25];

void solve(int sum, int idx) {
    if (idx == n) {
        if (sum == s) cnt++;
        return;
    }

    solve(sum + nums[idx], idx + 1);
    solve(sum, idx + 1);
}

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

    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> nums[i];

    solve(0, 0);

    if (s == 0) cnt--;

    cout << cnt;
}