[SW Expert] 2817. 부분 수열의 합

1) 생각

수열의 개수 N과 숫자 K가 주어진다. 수열에서 수를 합 하였을 때, K가 되는 경우의 수를 구하여라.

처음 생각

DFS를 통해 수열에서 그 숫자를 포함하고 가는경우와 포함하고 가지 않는 경우로 나누어 탐색을 진행한다.

▶재귀를 통해 구현하여 가지치기를 잘 해주어야 한다.

▶이 문제의 경우 숫자의 합이 k에 도달 했을 때, Index 변수가 N에 도달하였을 때, 마지막으로 숫자의 합이 k를 넘어 섰을 경우 return 해주었다.

2) 방안

1) 재귀를 통해 구현을 하였다.

▶반복문의 경우 충분히 큰 숫자까지 돌 수 있지만 재귀의 경우에는 10만 번 정도 이상을 들어가게 되면 스택 오버플로우 에러가 나게된다. 따라서 재귀를 사용한 탐색의 경우 항상 가지치기를 잘해 주어야한다.

▶이러한 문제는 재귀를 통해 간단히 나타낼 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution{
    static int n,k;
    static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=tc;i++) {
            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 j=0;j<n;j++)
                arr[j] = Integer.parseInt(st.nextToken());
            result = 0;
            solve(0,0);
            sb.append("#"+i+" "+result+"\n");
        }
        System.out.println(sb);
    }
    
    static int result;
    private static void solve(int idx,int sum) {
        if(sum==k) {
            result++;
            return;
        }
        if(sum>k || idx>=n) return;
        // 자기 자신을 포함
        solve(idx+1,sum+arr[idx]);
        // 자기 자신을 미포함
        solve(idx+1,sum);
    }
}