JArchive 프로그래밍 일기

문제

부분수열의 합 백준 1182번

리뷰

혼자 힘으로 못풀겠어서 다른 분들 코드를 봤다.

N개의 숫자를 입력받아서 합이 S가 되는 부분 집합의 개수를 구하는 문제다.

부분 집합을 만들 줄 알아야 한다.

인덱스 0부터 N-1 까지 순회하면서, 현재 인덱스의 숫자를 집합에 '포함' / '미포함' 을 구분하여 재귀호출한다.

탐색 함수의 시그니처는 현재 index를 나타내고, 공집합이면 안되니까 포함시킨 숫자의 cnt를 세준다.

void dfs(int index, int sum, int cnt)

코드

#include <iostream>
#include <algorithm> 
using namespace std;


int N, S, answer;
int a[21];

void dfs(int index, int sum, int cnt){

    if(index == N){
        if(S == sum && cnt > 0) {
            answer++;
        }
        return;
    }

    dfs(index+1, sum+a[index], cnt+1); // 포함한다.
    dfs(index+1, sum, cnt); // 포함 안한다  
} 

int main(void){

    cin >> N >> S;

    for(int i = 0; i < N; i++){
        scanf("%d", &a[i]);
    } // 수열의 수를 입력받는다. 

    dfs(0, 0, 0);

    cout << answer;

    return 0;
}