문제 링크

접근 방법

• 깊이가 N이면 그때 합이 S인지 확인
• 현재 arr[idx]를 합한 경우도 고려해야되고 합하지 않은 경우도 고려해야 함
• S == 0일 때, 공집합이 생기므로 정답-1 해줘야 함

공집합이 생기는 경우

idx=0, total=0
 → 선택X
idx=1, total=0
 → 선택X
idx=2, total=0
 → 선택X
idx=3, total=0
 → 선택X
idx=4, total=0
 → 선택X
idx=5 == N → total == S(0)

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1182_부분수열의합_S2 {
    static int N, S, answer;
    static int[] arr;

    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());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        dfs(0, 0);

        if (S == 0)
            answer--;
        System.out.println(answer);
    }

    public static void dfs(int idx, int total) {
        if (idx == N) {
            if (total == S)
                answer++;
            return;
        }

        // 현재 원소를 선택하는 경우
        dfs(idx + 1, total + arr[idx]);

        // 현재 원소를 선택하지 않는 경우
        dfs(idx + 1, total);
    }
}