[Baekjoon]백준 1182번 부분수열의 합

1182번 부분수열의합 문제 풀이

문제

• N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절대값은 100,000을 넘지 않는다.

출력

• 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제

입력
5 0 
-7 -3 -2 5 8 

출력
1

해결방법

• 재귀함수를 사용하여 모든 원소들에 대한 부분집합을 전부 만들어 본 후에 입력한 값이랑 같은지 비교하는 방법을 사용했다.

변수&함수	내용
num	정수의 개수
result	구해야할 정수
a	원소를 저장시킬 배열
go(a,index,sum)	배열,index,부분집합의 합을 인자 값으로 받는 함수
ans	부분집합의 합이 result가 될 때 증가시키는 변수

• go()는 원소가 부분집합에 포함될 때와 아닐 때를 구분하여 재귀한다.

  1. 포함할 때 : go(a,index+1,sum+a[index])
  2. 포함되지 않을 때 : go(a,index+1,sum)

• 정답을 찾은경우 : num==index && sum == result

• 종료조건 : num == index

• 우리가 구해야할 정수가 '0'인경우 공집합에 대해서 결과 값이 '1'이 추가되기 때문에 최종 결과에서 '-1'을 해주어야 한다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int ans = 0;
int num;
int result;
void go(vector<int> a, int index, int sum) {
    if (num == index) {
        if (sum == result) {
            ans += 1;
        }
        return;
    }

    go(a, index + 1, sum + a[index]);
    go(a, index + 1, sum);
}

int main() {
    cin >> num >> result;
    vector<int> a(num);
    for (int i = 0; i < num; i++) {
        cin >> a[i];
    }
    go(a, 0, 0);
    if (result == 0) ans -= 1;
    cout << ans << '\n';
    return 0;
}