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

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

풀이

 

부분집합을 다 구하면 된다.

주의할 점은 S = 0인 경우 공집합도 가능하니까 이때는 total을 하나 빼야 한다.

public class BOJ_1182 {
	static int N, S;
	static int[] numbers;
	static int total = 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());
		numbers = new int[N];
		
		st = new StringTokenizer(in.readLine()," ");
		for(int i=0;i<N;i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		subset(0, new boolean[N]);
		if(S == 0)
			System.out.println(total-1);
		else
			System.out.println(total);
	}
	static void subset(int cnt, boolean[] visited) {
		if(cnt == N) {
			int sum = 0;
			for(int i =0;i<N;i++) {
				if(visited[i]) {
					sum += numbers[i];
				}
			}
			if(sum == S) total++;
			return;
		}
		visited[cnt] = true;
		subset(cnt+1, visited);
		visited[cnt] = false;
		subset(cnt+1, visited);
	}
}