1182번 : 부분수열의 합 [Java]

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

1182번: 부분수열의 합

해결 방법

DFS를 통해 원소를 선택하거나 선택하지 않는 경우를 따져본다. 

 

주의할 점

S가 0인 경우엔 공집합을 빼줘야 하기 때문에 ans-1

 

전체 코드

import java.util.Scanner;

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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		S = sc.nextInt();
		arr = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = sc.nextInt();

		dfs(0, 0);

		System.out.println(S == 0 ? ans - 1 : ans);

	}

	private static void dfs(int dep, int sum) {
		if (dep == N) {
			if (sum == S)
				ans++;
			return;
		}

		dfs(dep + 1, sum + arr[dep]);
		dfs(dep + 1, sum);
	}
}