BOJ#1182 부분집합의 합

BOJ#1182 부분집합의 합

* 문제

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

* 풀이

처음에는 조합을 이용해서 풀었습니다. (160ms)

집합에서 1개를 고르는 경우, 2개를 고르는 경우, ...., N개를 고르는 경우

두번째 풀때는 집합의 각 원소의 2가지 경우에 대해(고르는 경우, 고르지 않는 경우)

재귀 함수 호출로 답을 구하였습니다. (76ms)

주의할 점 : S가 0인 경우에는 공집합도 카운트 될 수 있음

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231182_SumOfSubsets/src/Main.java

import java.io.*;
import java.util.StringTokenizer;

/**
 * BOJ#1182 부분집합의 합
 * https://www.acmicpc.net/problem/1182
 */

public class Main {

    static int N;
    static int S;
    static int cnt = 0;
    static int[] numArr = new int[21];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {

            numArr[i] = Integer.parseInt(st.nextToken());
        }

        solve(0, 0);

        // S가 0인 경우 공집합도 포함되므로 개수에서 -1을 빼준다.
        if (S == 0) {
            cnt -= 1;
        }

        System.out.println(cnt);
    }

    static void solve(int sum, int step) {

        if (step == N) {

            if (sum == S) cnt++;
            return;
        }

        solve(sum + numArr[step], step + 1);
        solve(sum, step + 1);
    }
}