[백준] 1182. 부분수열의 합(실버2)

백준(실버2) - 1182. 부분수열의 합(실버2)

풀이

문제에서 어떻게 풀어야하는지 바로 힌트를 줬다.
부분수열로 풀었다! 비트 마스크로 푸는 방법도 있던데 추가적으로 학습해봐야겠다!

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

public class Main {
	static int[] numbers;
	static long sum,s,n,count;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		numbers = new int[(int) n];
		st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<n; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		count = 0;
		subset(0,0);
		System.out.println(count);
	}
	
	public static void subset(int start, long sum) {
		if(start == n)
			return;
		if(sum+numbers[start] == s) {
			count++;
			
		}
		
		//선택했을 때
		subset(start+1, sum+numbers[start]);
		
		//선택하지 않았을 때
		subset(start+1, sum);
	}

}