BOJ : 1182 부분집합의 합

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

브루트 포스로 풀기엔 생각보다 까다로운 면이 있다. 

부분 집합을 구할 때는 DP 혹은 비트마스크를 이용해서 많이 구하기 때문에

부분집합을 구하는 기법을 알아두면 다른 곳에서도 유용하게 사용할 수 있다.

나는 비트마스크로 풀었는데 비트마스크를 이용해 부분집합을 구하는 코드는 아래와 같다.

int N[4] = {1, 2, 3, 4};

for(int i=0; i < (1 << (N)); i++){
        for (int j=0; j<N; j++){
            if (i & (1 << j)){
                printf("%d ",A[j]);
            }
        }
        printf("\n");
    }
}

출력하면 공집합까지 출력되는 것을 볼 수 있다.

이를 응용해서 코드를 작성해보았다.

#include <stdio.h>
int main(){
    int N,S,A[21],cnt=0,sum;
    scanf("%d %d",&N,&S);
    for(int i=0; i<N; i++) scanf("%d",&A[i]);
    for(int i=1; i < (1 << (N)); i++){
        sum=0;
        for (int j=0; j<N; j++){
            if (i & (1 << j)){
                sum+=A[j];
            }
        }
        if(sum == S) cnt++;
    }
    printf("%d\n",cnt);
}