부분수열의 합

나의 논리

부분수열 시리즈같아서 재귀함수로 코딩을 할 로직이 생각났다.
더 깊은 함수 호출 스택의 결과를 모아서 상위 호출스택으로 모아서 보내는 로직을 생각했고
하위 호출스택에서 만들어지는 모든 중간값, 이 문제의 경우에서는 부분수열의 합, 을 벡터의 참조값에 모두 저장 한뒤 set 컨테이너에 옮겼다가 다시 벡터로 옮겼다.
자연수 1부터 시작하는 변수 k를 차례로 벡터와 비교하면서 벡터의 원소와 변수가 불일치하는 부분이 바로 벡터에 들어가야 할 가장 작은 자연수다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int nums[20];
int n;
void solve(int prev,int sum,vector<int>& ret)
{
    for(int next = prev + 1; next <n; ++next){
        ret.push_back(sum+nums[next]);
        solve(next, sum+nums[next],ret);
    }
    
}
int main()
{
    vector<int> ret;
    cin>>n;
    for(int i=0; i<n; ++i) cin>>nums[i];
    for(int i=0; i<n; ++i){
        ret.push_back(nums[i]);
        solve(i, nums[i],ret);
    }
    
    set<int> s;
    for(int i=0; i<ret.size(); ++i){
        s.insert(ret[i]);
    }
    
    ret.clear();
    copy(s.begin(), s.end(), back_inserter(ret));
    int k = 1;
    int ans = 0;
    for(int i=0; i<ret.size(); ++i){
        if(k != ret[i]) break;
        k++;
    }
    ans = k;
    cout<<ans;
}

정답 논리

바로 정답을 맞췄지만 더 간단하고 직관적인 코드를 발견해서 참고하고자 한다.

출처

https://100100e.tistory.com/188

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool range[20 * 100000];
int S[20];
int N;
void solve(int begin, int sum)
{
    if (begin == N) {
        range[sum] = true;
        return;
    }
    solve(begin + 1, sum + S[begin]);
    solve(begin + 1, sum);
}
int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        cin >> S[i];
    }
    solve(0, 0);
    
    int start = 0;
    while (1)
    {
        if (range[start] != 1) {
            cout << start << "\n";
            return 0;
        }
        start++;
    }
}

최악의 경우 발생 할 수 있는 자연수는 20 100,000이다. 1~20100,000 범위의 자연수를 체크 할 수 있는 bool 타입의 배열을 만든다.

그리고 재귀함수에서 n번째 배열의 원소를 사용하는 경우와 사용 하지 않는 경우 2가지에 대해 재귀 호출을 한다. 해당 원소를 사용하여 sum을 만들던 안만들던 해당 원소에 대한 결정은 내려졌으므로 begin+1을 하여 다음 원소로 진행을 한다. (한다..안한다.. 이렇게보니 비트마스크를 사용해서 풀 수 있겠다.)
그렇게 해서 모든 N개의 원소에 대해 한다/안한다의 결정이 다 됬으면 여태껏 해온 sum에 대해 true 대입한다. 해당 자연수는 연산의 결과로 나타난다는 것이다.

그리고 1~20*100,000 범위를 가진 자연수 배열을 제일 처음부터 확인해가며 나타나지 않은 (false값) 자연수를 출력하고 바로 종료한다.