[SWEA] 2817. 부분 수열의 합

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

접근 방법

DFS와 조합으로 check 없이 풀었다.

먼저 정렬 후 K보다 작거나 같은 최대 수를 배열의 끝점으로 정해 혹시 모를 불필요한 탐색을 줄였다.

input에 따라 어쩌면 불필요한 과정일지도 모른다.

5개의 수가 있을 경우 5 만큼 반복 재귀를 이중으로 하기 때문에

5개의 수 중 하나를 고르고 나면 4개 중 고르고 그 다음은 3개 중 고르는 식을 썼다.

하나의 조합은 한 번의 탐색이면 되니까, 재귀 이전 인덱스보다 1이 큰 수부터 시작해 한 번 필참한 수는 제외했다.

 

소스 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static int K;
    static int cnt;
    static int idx;
    static int[] n;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t=1; t<=T; t++) {
            int N = sc.nextInt();
            K = sc.nextInt();
            cnt = 0;
            idx = N;
            n = new int[N];
            for(int i=0; i<N; i++)
                n[i] = sc.nextInt();
             
            Arrays.sort(n);
            for(int i=0; i<N; i++) {
                if(n[i] > K) {
                    idx = i;
                    break;
                }
            }
             
            for(int i=0; i<idx; i++) {
                bfs(i, n[i]);
            }
            System.out.println("#" + t + " " + cnt);
        }
    }
    static void bfs(int j, int s) {
        if(s == K) { cnt += 1; return; }
        else if(s > K) { return; }
         
        for(int i=j+1; i<idx; i++) {
            bfs(i, s+n[i]);
        }
    }
}