[백준] 1182번:부분수열의 합 (Java 자바)

문제

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

1182번: 부분수열의 합

 

풀이 및 소스코드

 

시작할 때, sum이 0이기 때문에

s가 0으로 들어오게 되면 카운트가 +1 된다.

따라서 s==0 이라면 결과 값에서 -1을 해줘야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
	static int[] arr;
	static int n, s, res;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		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());
		}
		
		find_sum_s(0, 0, 0);
		if(s==0) {
			res -- ;
		}
		System.out.println(res);
	}
	
	public static void find_sum_s(int cnt, int start, int sum) {
		
		if(sum == s) {
			res++;
		}
		
		if(cnt == n) return;
		
		System.out.println("cnt : "+cnt+" "+"start : "+start+" sum : "+sum);
		for(int i=start;i<n;i++) {
			find_sum_s(cnt+1, i+1, sum+arr[i]);
		}
	}
	
}