BOJ 1182 부분수열의 합 [Java]

BOJ 1182 부분수열의 합

1. 문제 링크

https://www.acmicpc.net/problem/1182

2. 문제 해설

재귀를 이용해서 풀었다. 각 원소마다 더할 것인지 더하지 않을 것인지를 선택할 수 있고 그에 따라 재귀 함수가 계속 호출된다.
그러므로 시간복잡도는 O(2^n)이다. 최악의 경우에 n이 20이기에 주어진 시간 안에 충분히 해결할 수 있다.
재귀 함수의 매개 변수로 idx와 sum을 주어 현재 몇번째 idx에 위치해있고, 더한 값이 얼마인지를 담았다.
재귀 함수의 탈출 조건은 idx가 n과 같아지면 탈출하고, 만약 sum이 s와 일치하면 경우의 수 값 cnt를 +1 해준다.
문제 조건에서 부분수열의 크기가 양수여야하는 조건이 있으므로 만약 s가 0이라면 아무 것도 더해주지 않은 경우를 빼줘야한다.
그러므로 s가 0이면 cnt에서 -1을 해주고 아니면 cnt를 출력하면 된다.

3. 코드 보기

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

public class Main {
    static int n, s;
    static int cnt, ans;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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) {
            ans = cnt - 1;
        } else {
            ans = cnt;
        }

        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }

    static void DFS(int sum, int idx) {
        if (idx == n) {
            if (sum == s) {
                cnt++;
            }

            return;
        }

        DFS(sum, idx + 1);
        DFS(sum + arr[idx], idx + 1);
    }
}