[JAVA] SWEA 2817. 부분 수열의 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=2

SW Expert Academy

 

 

 

 

정답 

 

https://velog.io/@sua_ahn/SWEA-2817-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4%EC%9D%98-%ED%95%A9-Java

SWEA 2817 부분 수열의 합 (Java)

 

 - 종료 조건

 -> 현재 인덱스가 배열의 크기 N에 도달했을 때, 현재 합이 K와 같으면 1을 반환, 그렇지 않으면 0을 반환

 

- 현재 요소를 포함하는 경우와 포함하지 않는 경우 두 가지로 나누어 재귀 호출

- 두 경우의 수를 합산하여 반환 

 

import java.util.*;

public class Solution {
	public static int dfs(int arr[], int N, int K, int idx, int curSum )
	{
		//모든 요소를 다 고려했을 때 
		if(idx==N)
		{
			return curSum==K?1:0;
		}
		
		//현재 요소를 포함하는 경우 
		int include = dfs(arr,N,K,idx+1, curSum+arr[idx]);
		//현재 요소를 포함하지 않는 경우 
		int exclude = dfs(arr,N,K,idx+1,curSum);
		
		return include+exclude;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for (int t=1; t<=T; t++) {
			int N = sc.nextInt(); //자연수 수 
			int K = sc.nextInt(); //합이 k가 되는 수 
			int answer=0; //합이 k가 되는 수 
			
			int arr[] = new int[N];
			
			for(int i=0; i<N; i++)
			{
				arr[i] = sc.nextInt();
			}
			
			answer = dfs(arr,N,K,0,0);
			
			System.out.printf("#%d %d\n", t, answer);
		}
	}
}