[SW Expert Academy] 부분 수열의 합 (D3)

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

SW Expert Academy

import java.util.Scanner;

class Solution {

	public static int n, k, result;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {

			n = sc.nextInt();
			k = sc.nextInt();
			result=0;

			int num[] = new int[n];

			for (int i = 0; i < n; i++) {
				num[i] = sc.nextInt();
			}

			solution(0, 0, num);

			System.out.println("#" + tc + " "+result);
		}
	}

	public static void solution(int depth, int sum, int[] num) {
		if (sum > k) { //깊이를 덜 갔는데 초과하면 바로 리턴
			return;
		}
		if (depth == n) { //끝까지 갔는데 
			if (sum == k) { //합이 k면 결과++
				result++;
			}
			return;
		}
		solution(depth + 1, sum + num[depth], num); //현재 보는 값 포함
		solution(depth + 1, sum, num); //현재 보는 값 포함x
	}
}

 

dfs로 해결했다.