[Baekjoon Online Judge] 1182 - 부분수열의 합 / Java

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

1182번: 부분수열의 합

풀이1

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

public class Main {
	static int answer = 0, N, S, arr[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		subset(0, 0);
		System.out.println(S == 0 ? --answer : answer);
	}

	public static void subset(int cnt, int sum) {
		if (cnt == N) {
			if (sum == S) {
				answer++;
			}
			return;
		}

		subset(cnt + 1, sum + arr[cnt]);
		subset(cnt + 1, sum);
	}
}

풀이2 - boolean isSelected[] 배열 사용

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

public class Main {
	static int answer = 0, N, S, arr[];
	static boolean isSelected[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new int[N];
		isSelected = new boolean[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		subset(0);
		System.out.println(S == 0 ? --answer : answer);
	}

	public static void subset(int cnt) {
		if (cnt == N) {
			int sum = 0;
			for (int i = 0; i < N; i++) {
				if (isSelected[i]) {
					sum += arr[i];
				}
			}
			if (sum == S) {
				answer++;
			}
			return;
		}

		isSelected[cnt] = true;
		subset(cnt + 1);
		isSelected[cnt] = false;
		subset(cnt + 1);
	}
}