백준 1182번: 부분수열의 합

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

1182번: 부분수열의 합

 

이 문제는 처음에 순열을 이용해서 일일이 위치값 변경하면서 더했는데 이럴경우 시간복잡도가 (n*n!)가 나와 시간초과가 나온다

그 다음으로 재귀함수를 구현해서 모든 부분집합을 구햇다. 시간복잡도는 (2^n-1)이 나오고 시간초과는 나오지 않았다.

함수에는 부분집합의 합과 배열 몇 번째인지 를 인자로 받고  

몇번쨰 배열 인자를 더하는 경우와 안더하는 경우를 나누어서 재귀를 했다.

탈출조건은 배열인지가 끝에 도달하면 탈출하게 했다.

코드를 보자

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,s;
int ans;
void check(vector<int>& v,int sum,int i){
    if(i==n){                            //배열의 끝을 도달했을 떄
        if(sum==s){                      //s와 합이 같으면 1증가
            ans++;
        }
        return;
    }
    check(v,sum+v[i],i+1);                //i번쨰 값을 더할때
    check(v,sum,i+1);                      //i번쨰 값을 안 더할때
}
int main(){
    cin>>n>>s;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    check(v,0,0);
    if(s==0){                        //s가 0이면 공집합은 빼야하므로 -1해준다
        cout<<ans-1;
    }
    else{
        cout<<ans;
    }
}