[비트마스크] BOJ 1182 부분수열의 합

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

1182번: 부분수열의 합

- 문제 파악

정수 두개와 첫번째 정수 크기만큼의 수열을 입력한다. 입력된 수열을 조합하여 만든 수열의 합이 두번째 수열이 되는 경우의 수를 출력하라. 중복은 없다.

 

- 나의 풀이

백트래킹으로 풀면 된다고 생각했으나, 중복문제 그리고 시간 초과로 인해서 제대로된 결과를 얻을 수 없었다.

아래 정답은 재귀를 활용한 코드인데, 아이디어가 괜찮은것 같다. 일반적인 백트래킹보다 생각을 덜 할 수 있다.

 

- 정답

#include "bits/stdc++.h"

using namespace std;

int arr[22];
int ans;
int n, s;

void func(int k, int val)
{
    if (k == n)
    {
        if (val == s)
            ans++;

        return;
    }

    func(k + 1, val);
    func(k + 1, val + arr[k]);

}



int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n;
    cin >> s;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    func(0,0);


    if (s == 0) ans--;

    cout << ans;


}