백준 BOJ 1182 부분수열의 합 [자바]

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

문제 분석

n개의 정수, 이 중 일부를 합쳤을 때 s가 되는 경우의 수는?

 

입력

정수 n 정수 s

주어진 수 n개

 

문제 풀이

주어진 입출력 예시를 보면 주어지는 수 들이 정렬되어 있는것처럼 보이지만,

문제의 어디에도 그런 말이 없다.

결론 : 무식하게 브루트포스로 모든 부분수열의 합을 계산

 

나는 재귀함수를 사용하여, idx를 0부터 n까지 올리면서,

idx번 수를 더하거나 안 더할 때, 목표값에 도달할 수 있는가를 확인하는 방식으로 풀었다.

 

단, 여기 딱 한가지 예외가 있는데,

목표값 s가 0일 때다.

s가 0이면, 주어진 배열에서 아무 숫자도 선택하지 않았을 때도 s에 도달했다고 판단하는데,

이 값을 빼 줘야 한다.

 

 

전체 코드

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

public class BJ1182_부분수열의합 {
	static int count = 0;
	static int n;
	static int s;
	static int[] nums;
	
	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());
		nums = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		powerset(0, 0);
		if(s == 0) count--;
		System.out.println(count);
	}
	public static void powerset(int sum, int idx) {
		if(idx == n) {
			if(sum == s) {
				count++;
			}
			return;
		}
		powerset(sum, idx + 1);
		powerset(sum + nums[idx], idx + 1);
	}
}