[BOJ 길라잡이/Java] 13일차 #1182 부분수열의 합

알고리즘 분류

- 브루트포스 알고리즘

- 백트래킹

 

주어진 수열의 부분수열 중 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제다.

문제를 보고 depth를 하나씩 더해나가면서 백트래킹으로 풀어야겠다

까지는 생각했는데 그걸 어떻게 구현해야 할지는 감이 안 왔다.

 

구글링 통해 알아낸 방법을 이해하려 노력했다.

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

class Main {
    static int N, S, cnt;
    static int[] arr;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0);
        if (S == 0) cnt--; // 공집합 제외
        System.out.println(cnt);
                
    }

    public static void dfs(int depth, int sum) {
        if (depth == N) {
            if (sum == S) cnt++;
            return;
        }

        dfs(depth + 1, sum + arr[depth]); // 원소를 선택한 경우
        dfs(depth + 1, sum); // 원소를 선택하지 않은 경우
    }
}

 

이 함수는 모든 부분 수열을 탐색한다.

(2^N개의 조합을 체크)

선택 or 선택하지 않음의 2갈래로 분기하는 재귀