백준 1182번 부분집합의 합

문제 링크입니다: https://www.acmicpc.net/problem/1182

부분집합의 합을 구할 때 해당 인덱스에 있는 숫자를 더하는 경우가 있고 안 더하는 경우가 있는데 이를 모두 고려해준다면 쉽게 답을 구할 수 있는 문제였습니다.

개인적으로 종만북에 나온 코드들에 익숙해져 반복문보다는 재귀호출이 더 쉽게 느껴지네요.

#include <iostream>

using namespace std;

 

const int MAX = 20;

 

int N, S;

int arr[MAX];

int result = 0;

 

void numOfSubset(int idx, int sum)

{

        sum += arr[idx]; //우선 해당 숫자를 더한다

 

        //기저사례: 범위 초과시

        if (idx >= N)

                 return;

        //조건 성립시

        if (sum == S)

                 result++;

 

        //해당 숫자를 안 더했을 경우

        numOfSubset(idx + 1, sum - arr[idx]);

        //해당 숫자를 더헀을 경우

        numOfSubset(idx + 1, sum);

}

 

int main(void)

{

        cin >> N >> S;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        numOfSubset(0, 0);

 

        cout << result << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~