백준 1182: 부분수열의 합

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

1182번: 부분수열의 합

이 문제는 멱집합을 구하는 알고리즘을 조금 변형하면 풀 수 있다. k번 째 원소를 뽑거나 안 뽑거나에 따라 합이 달라진다. 

k번째 원소를 합한 값, 합하지 않은 값을 넘겨 재귀호출한다.

 

import java.util.*;
public class Main {
	static int powerSet(int[] arr, int s, int target, int k) {
		int cnt=0;
		
		if(k==arr.length) {
			if(s==target)
				return 1;
			else
				return 0;
		}

		cnt+=powerSet(arr, s, target, k+1);
		cnt+=powerSet(arr, s+arr[k], target, k+1);
		
		return cnt;
	}


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int s = sc.nextInt();
		int[] arr = new int[n];

		for(int i=0; i<n; i++)
			arr[i] = sc.nextInt();
		
		int count = powerSet(arr, 0, s, 0);
		
		if(s!=0)
			System.out.println(count);
		else
			System.out.println(count-1); //공집합까지 카운트하는 경우
	}
}

s가 0인 경우에는 공집합인 경우에도 카운트하므로 1을 빼줘야 한다. 처음에는 이 부분을 생각하지 못해 틀렸다.