[백준/C++] 1182번: 부분수열의 합(S2)

문제

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

1182번: 부분수열의 합

 

사용한 알고리즘

2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹

-> 백트래킹.
    모든 상태에 대해 어떤 조건을 따져주는 문제

 

풀이

현재 보고있는 원소를
'포함시킨다/포함시키지 않는다' 라는 두가지 경우로 나누어 생각해보면 된다.

 

소스코드 

#include <iostream>
typedef long long ll;
using namespace std;
int n,s,arr[21];
int ans;

void solve(int idx, int sum) { //이번에 포함시킬지 선택할 원소의 idx, 지금까지 고른 수들의 합
    if (idx == n) {  //인덱스는 n-1까지이므로 인덱스n은 포함시킬 수 없음
        if(sum==s) ans++;
        return;
    }

    solve(idx+1, sum);
    solve(idx+1, sum+arr[idx]);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n>>s;
    for(int i=0; i<n; i++) cin>>arr[i];
    solve(0,0);

    //크기가 양수인 부분수열(!=공집합)만 구해야하는데
    //s==0이면 아무것도 고르지않았을때도 ans++하게되므로 ans--해줘야힘
    if(s==0) ans--;
    cout<<ans;
    return 0;
}

 

 

다른 풀이

    int n,s,arr[25];
    int ans=0, sum=0;
    
    void solve(int idx){ //이번에 포함시킬지를 선택하는 원소의 인덱스
        if(idx==n) return; //인덱스는 n-1까지이므로 n인덱스를 포함시키는 경우는 따지면 안됨
        if(sum+arr[idx]==s) ans++; //이번 인덱스를 포함시켜 합이 s가 되는 경우 카운트를 1증가시킴
        solve(idx+1); //idx번째 원소를 합에 포함시키지 않고 다음 인덱스에 대한 상태로 전이함 
        sum+=arr[idx];
        solve(idx+1); //idx번째 원소를 합에 포함시키고 다음 인덱스에 대한 상태로 전이함
        sum-=arr[idx]; //합을 idx번째 원소를 포함시키지 않은 상태로 되돌려줌
    }