1182 부분수열의 합 (JAVA)

• 쓴다? 안쓴다? 유형의 문제이다.
• 모든 경우의 수를 따져봐야 하는 문제이기 때문에 check 배열은 사용하지 않는다.

public class Main {

    static int n,cnt = 0;
    static void dfs(int L, int[] arr, int sum,int target){
        if(L == n){
            if(sum == target)
                cnt++;
            else
                return ;
        }
        else{
        	// 다음 수를 sum에 포함 시킨다?
            dfs(L+1, arr, sum, target);	
            // 다음 수를 sum에 포함 시키지 않는다?
            dfs(L+1, arr, sum+arr[L], target);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int target = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; ++i){
            arr[i] = sc.nextInt();
        }
        dfs(0,arr,0,target);
        if(target == 0)
            System.out.println(cnt-1);
        else
            System.out.println(cnt);
    }
}