[BJ] 1182 : 부분수열의 합

       문제 요약        

- 문제

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

N개의 정수로 이루어진 수열이 있을 때,

크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

- 입출력

5 0
-7 -3 -2 5 8

 

         아이디어        

 

 

종료조건(N), 정답관련 처리 

포함하는 경우, 포함하지 않는 경우 2가지의 경우의 수 

         소스코드        

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
	static int N, S;
	static int[] box;
	static int ans;
	
	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()); // 수열의 원소를 다 더한 값

	    box = new int[N];
	    st = new StringTokenizer(br.readLine());
	    for(int i = 0; i < N; i++) {
	    	box[i] = Integer.parseInt(st.nextToken());
	    }
	    dfs(0, 0, 0);
	    System.out.println(ans);
	}
	
	static void dfs(int n, int s, int cnt) {
		if(n == N) {
			if(s == S && cnt > 0) {
				ans += 1;
			}
			return;
		}
		dfs(n + 1, s + box[n], cnt + 1); // 가지치기 조건 (선택)
		dfs(n + 1, s, cnt); // 가지치기 조건(선택x)
	}
}