1182번

1182번 - 부분 집합의 합

1. 재귀함수를 이용해서 풀이

2. 비트마스크를 이용해서 풀이

for문에서는 0인 공집합을 빼고 모든 부분집합을 도는 조건문이다.

아래의 for문을 

 for (int subset = set; subset; subset = set & (subset - 1))

아래처럼 바꿔도 동일하다.

for(int subset=1;subset<(1<<N);subset++)

<정답 코드 - 재귀함수>

#include<iostream>
#include<algorithm>
using namespace std;
 
int N;
int S;
int D[21];
int ans;
void dfs(int n, int sum)
{
    
    if (n == N)
    {
        if (sum == S)
        {
            ans += 1;
        }
 
        return;
    }
 
    dfs(n + 1, sum + D[n]);
    dfs(n + 1, sum);
 
 
    return;
}
int main()
{
    cin >> N >> S;
 
    for (int i = 0; i < N; i++)
    {
        cin >> D[i];
    }
    dfs(0, 0);
    if (S == 0)
    {
        ans -= 1;
    }
    cout << ans << endl;
    return 0;
}

<정답 코드 - 비트마스크>

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
    int N, S, ans = 0;
    vector<int> v;
 
    cin >> N >> S;
 
    v.resize(N);
 
    for (int i = 0; i < N; i++)
    {
        cin >> v[i];
    }
 
    int set = (1 << N) - 1;
 
    for (int subset = set; subset; subset = set & (subset - 1))
    {
       
        int sum = 0;
        for (int i = 0; i < N; i++)
        {
            if ((1 << i)&subset)
            {
                sum += v[i];
            }
        }
 
        if (sum == S)
        {
            ans += 1;
        }
    }
 
    cout << ans << endl;
    
    return 0;
}