[완전탐색] 백준 1182 부분수열의 합 JAVA (전위순회)

package com.test.exhaustiveSearch;

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

public class ES_10_1182 {
    // [완전탐색] 백준 1182 부분수열의 합 JAVA
    static int N;
    static int S;
    static int[] arr;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]); //1~20
        S = Integer.parseInt(input[1]);
        input = br.readLine().split(" ");
        arr = new int[N];
        for (int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        backtracking(0, 0);
        System.out.println(count);
    }
    private static void backtracking(int idx, int beforeSum) {
        if (idx == N) return;
        if (arr[idx] + beforeSum == S) count++;
        backtracking(idx + 1, beforeSum);
        backtracking(idx + 1, beforeSum + arr[idx]);
    }
}