[백준] 1186 부분수열의 합 java

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

public class Main {
    static int N;
    static int S;
    static int ans = 0;
    static int[] arr;
    static StringTokenizer st;

    public static void backtracking(int idx, int sum) {
       if(idx == N) {
           if(sum == S) {
               ans++;
           }
           return;
       }
       backtracking(idx+1, sum);
       backtracking(idx+1, sum+arr[idx]);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());
        }

        backtracking(0, 0);
        if(S == 0) ans--;
        System.out.println(ans);
    }
}

이 문제의 핵심은 재귀로 경우의 수를 찾을 때 해당 원소를 더하지 않는 경우와 원소를 더하는 경우를 나누는 것이다.

 

이런식으로 해당 원소마다 2가지의 경우의 수로 가지를 늘려 이진 트리 구조가 나오게 된다.

 

그러다가 마지막 원소까지 경우의 수를 구했을 때 해당 합이 S와 같을 경우에는 카운트를 올려주면 된다.

 

그리고 마지막에 S가 0일 경우에는 공집합이 카운트에 하나가 포함이 되므로 빼주고 출력하면 된다.