[문제] 백준 1182번 부분수열의 합

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

내 풀이

 

부분집합 구하는 공식으로 풀면 빠르게 풀리는 문제!

단, 합이 0일 때 공집합 제외해주는 것 잊지 말자

public class BOJ_1182 {
	static int N, S;
	static int[] arr;
	static int answer = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new int[N];
		
		st=new StringTokenizer(in.readLine()," ");
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		subset(0,new boolean[N]);
		System.out.println(answer);
	}
	
	// 부분집합 다 구해보기
	static void subset(int cnt, boolean[] checked) {
		if(cnt==N) {
			int sum=0;	// 부분집합의 총합
			int count = 0;
			for(int i=0;i<N;i++) {
				if(checked[i]) {
					sum += arr[i];	
					count++;
				}
			}
			// 공집합 제외
			if(sum==S && count>0) answer++;
			return;
		}
		
		checked[cnt] = true;
		subset(cnt+1, checked);
		checked[cnt] = false;
		subset(cnt+1, checked);
	}
}