[BOJ] #1182 부분수열의 합

시간 제한	메모리 제한	정답 비율
2 초	256 MB	44.845 %

 

1182번: 부분수열의 합

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

메모리	시간
1988 KB	4 ms

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
 
int n, s, ans;
int arr[30];
void func(int idx, int sum) {
    if (n == idx) {
        if (s == sum) {
            ans++;
        }
        return;
    }
    func(idx + 1, sum + arr[idx]);
    func(idx + 1, sum);
}
int main() {
    scanf("%d%d",   n,   s);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr[i]);
    }
    func(0, 0);
    if (s == 0) ans--;
    printf("%d", ans);
 
    return 0;
}

 

 

비슷하지만 더 효율적인 방법

메모리	시간
1116 KB	0 ms

#include <stdio.h>
int n,s,cnt,a[30];
 
void find(int i,int sum){
    if(sum+a[i]==s) cnt++;
    if(i==n-1) return;
    find(i+1,sum); find(i+1,sum+a[i]);
}
 
int main(){
    scanf("%d %d",&n,&s);
    for(int i=0; i<n; i++){
        scanf("%d",&a[i]);
    }
    find(0,0);
    printf("%d",cnt);
}