백준 1182 : 부분수열의 합 _자바 Java

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

1182번: 부분수열의 합

 

---

 

* 부분 수열

원소 {A, B, C} 라면,  

 depth=0일 때는 아무것도 선택하지 않았을 때, 부분수열 = {Ø}

 depth=1일때는  이전 부분수열에 A를 가졌냐 안 가졌나로 나누어짐. 부분수열 = {A}, {Ø}

 depth=2일 때는  이전 부분수열에 B를 가졌냐 안 가졌나로 나누어짐. 부분수열 = {AB}, {A}, {B}, {Ø}

 depth=3일 때는  이전 부분수열에 C를 가졌냐 안 가졌나로 나누어짐. 부분수열 = {ABC}, {AB}, {AC}, {BC}, {A}, {B}, {C}, {Ø}

 

이런 식으로 진행이 된다. 

import java.io.*;
import java.util.*;

public class Main {
	
	static int N,S,cnt=0;
	static int[] num;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();	//정수 개수 
		S = sc.nextInt();	//목표 합이 되는 수
		num= new int[N];	//정수 담는 배열 

		for(int i=0;i<N;i++)
			num[i]=sc.nextInt();
		
		dfs(0,0);
		
		if(S==0)	//부분수열의 크기가 0일때를 고려
			cnt-=1;
		System.out.println(cnt);
		
	}// main()
	
	static void dfs(int depth, int sum) {
		if(depth==N) {
			if(sum==S)	cnt++;
			return;
		}
		
		dfs(depth+1,sum+num[depth]);	//지금 위치원소를 선택 했거나
		dfs(depth+1,sum);				//안했거나
	}
	
	
}// class Main