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

각각의 수를 포함할지 안 할지를 해보면서 합이 K가 되면 카운팅 해주는 식으로 짰다.
N이 최대 20이기 때문에 2^20으로 시간 초과가 나지 않는다.

import java.util.*;
class Solution
{
    static int cnt = 0;

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


        int T = sc.nextInt();
        for(int tc=1; tc<=T; tc++){
            sb.append("#").append(tc).append(" ");

            int N = sc.nextInt();
            int K = sc.nextInt();

            ArrayList<Integer> list = new ArrayList<>();
            for(int i=0; i<N; i++){
                list.add(sc.nextInt());
            }
            cnt = 0;
            solve(N, K, 0, 0, list);
            sb.append(cnt).append("\n");
            }
        System.out.println(sb);
	}
    static void solve(int N, int K, int i, int sum, ArrayList<Integer> list){
        if(sum == K){
            cnt++;
            return;
        }
        if(i >= N){
            return;
        }
        solve(N, K, i+1, sum + list.get(i), list);
        solve(N, K, i+1, sum, list);
    }
}