부분수열의 합 14225

문제

접근 방법

2^20의 경우는 범위 안에서 해결된다. 하지만 모든 수가 10만일 시 200만이라는 값이 나온다. 그러면 지역 변수 배열로는 해결이 안 되기에 다른 방법을 사용해야 한다.
다른 방법으로 해결한 뒤 1부터 가능한지 아닌지를 확인하며 올라오면 된다.

코드

#include <iostream>
bool visted[2000001];
int nums[20];
using namespace std;
int N, num;
void make(int idx, int sum)
{
    if (idx == N)
    {
        visted[sum] = true;
        return;
    }
    make(idx + 1, sum + nums[idx]);
    make(idx + 1, sum);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> num;
        nums[i] = num;
    }
    make(0, 0);
    for (int i = 1; i < 2000001; ++i)
    {
        if (!visted[i])
        {
            cout << i;
            break;
        }
    }
}

풀이

전역변수로 가능한 것을 어렴풋이 느꼈지만, set으로 해보고 싶었다. set에 추가해주고 1부터 값이 존재하는지 확인하며 증가시켜줬다. 해결은 했지만, set은 자동으로 정렬하기에 시간을 더 잡아먹었다. (200ms 이상의 시간이 나왔다)
정렬하는 과정이 필요 없는 전역 변수 bool 배열을 사용하면 시간이 많이 줄어든다. (8ms가 나왔다)