부분수열의 합 1182

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

완전탐색, 깊이우선 탐색, 이진 탐색, 방식으로 풀었다
자기자신 중복 X( 1원소 하나인데 1+1 하는경우 나오면 안된다)
조합 중복 X( 1+2 는 2+1 과 같다)

만약 다음과 같이 입력을 했다면
3 0
1 2 3

조합되는 경우는 다음과 같다. 이것은 재귀함수를 사용하여 이진트리를 깊이우선 탐색 하는 순서와 같다
1
1 2
1 2 3
1 3
2
2 3
3

하나만 더하는 경우, 두개 더하는 경우, 세개 더하는 경우가 있다
그래서 재귀함수를 사용해 이진탐색으로(현재 개수 만 더하는 경우, 하나더 더하는 경우로) 나누는 함수를 구현하였다. 다음 그림과 같은 모양으로 재귀탐색을 하게된다.

import java.io.*;

public class Main {

    static int[] inputArr;
    static int[] arr;
    static boolean[] checked;
    static int N;
    static int S;

    static int ans;


    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]);
        S = Integer.parseInt(input[1]);

        inputArr = new int[N];
        checked = new boolean[N];
        arr = new int[N];

        input = br.readLine().split(" ");
        for(int i = 0; i < N; ++i)
        {
            inputArr[i] = Integer.parseInt(input[i]);
        }

        dfs(0, 1, 0);

        System.out.println(ans);

    }

    public static void dfs(int depth, int targetdepth, int start)
    {
        if(depth == targetdepth)
        {
            int sum = 0;

            for(int i =0; i < depth; ++i)
            {
                sum += arr[i];
            }

            if(S == sum)
                ans++;

            //testcode
            //for(int i = 0; i < depth; ++i)
            //{
            //    System.out.print((arr[i])+" ");
            //}
            //System.out.println();
            //

            return;
        }

        for(int i = start; i < N; ++i)
        {
            if(checked[i] == false)
            {
                checked[i] = true;
                arr[depth] = inputArr[i];
                dfs(depth+1, targetdepth, i);
                dfs(depth+1, targetdepth+1, i);
                checked[i] = false;
            }
        }
    }
}