백준 1182 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

부분 수열 이문제는 

 

1개부터 N개까지 모든 경우를 뽑아내서 더해서 합이 S와 같은 갯수가 몇개 인지 세면되는데

비트로 생각하면 이렇게 뽑히면 되는겁니다.

이렇게 해서 1인부분의 합이 S가 되는 것을 세면 되는 문제로 엄청 쉬워집니다.

무튼 오늘은 아래 소스가 로또 문제랑 비슷하니 로또 문제도 풀어보시고 이문제도 풀어보시면 좋을것 같습니다.

#include<stdio.h>
using namespace std;
int N, S;
int input[21];
int num[21];
int cnt = 0;
void dfs(int s,int idx) {
    if (idx > N)return;
    if (idx>=1&&idx <= N) {
        int ret = 0;
        for (int y = 0, ten = 1; y < N; y++,ten*=10) {
            if (num[y] == 1)ret += input[y];
        }
            if (ret == S)cnt++;
    }
    for (int i = s; i < N; i++) {
        if (num[i] == 0) {
            num[i] = 1;
            dfs(i+1,idx + 1);
            num[i] = 0;
        }
    }
 
}
int main(void) {
    scanf("%d %d", &N, &S);
    for (int i = 0; i < N; i++) {
        scanf("%d", &input[i]);
    }
    dfs(0,0);
    printf("%d", cnt);
    return 0;
}