[백준 1182] 부분수열의 합 <Java>

import java.util.Scanner;

public class 부분수열의합 {
	static int n,s,count;
	static int num[];
	static boolean visited[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();//n개의 정수로 이루어진 수열
		s = sc.nextInt();//부분수열의 합이 s
		num = new int[n];
		visited = new boolean[n];
		
		for(int i=0;i<n;i++) {
			num[i] = sc.nextInt();
		}
		powerset(0);
		if(s==0) count--;
		System.out.println(count);
	}
	
	static void powerset(int cnt) {
		if(cnt==n) {
			int sum=0;
			for(int i=0;i<n;i++) {
				if(visited[i]) {
					sum += num[i];
				}
			}
			
			if(sum==s) count++;
			return;
		}
		
		visited[cnt] = true;
		powerset(cnt+1);
		visited[cnt] = false;
		powerset(cnt+1);
	}
}