[SWEA / 부분 수열의 합 / JAVA]

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

SW Expert Academy

 

문제 접근

직전에 풀었던 문제랑 유사하다.

해당 인덱스의 값을 넣었을 때와 넣지 않았을 때의 합이 K와 같은지 비교하고 같다면 횟수 + 1해준다.

 

++ 합이 K가 되는 인덱스의 합을 찾았다면 뒤의 계산은 탐색할 필요없다 더해봤자 K보다 항상 클테니까

return쳐서 바로 포함안됐을 때로 탐색하러가기

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

public class Solution {
	static int N;
	static int K;
	static int[] arr;
	static int count;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 원소 갯수
			K = Integer.parseInt(st.nextToken()); // 목표 값
			
			arr = new int[N];
			
			st = new StringTokenizer(br.readLine());
		    for(int i=0; i<arr.length; i++) arr[i] = Integer.parseInt(st.nextToken());
		    
            count = 0;
		    combi(0, 0);
		    System.out.println("#"+t+" "+ count);
		}
	}
	
	public static void combi(int idx, int sum) {
	
		if(sum == K) {
			count++;
			return; // 이미 만들었으면 뒤의 계산은 볼 필요없다, return안시키면 바로 다음 인덱스가 포함 안됐을 경우에 이미 카운팅했던 합으 다시 카운팅하게 됨
		}
		if(idx == N) return;
		
		combi(idx+1, sum+arr[idx]);
		combi(idx+1, sum);
	}
}