[JAVA] 백준 (실버2) 1182번 부분수열의 합

링크

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

---

문제 설명

정답률 43.345%
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

---

입력 예제

5 0
-7 -3 -2 5 8

---

출력 예제

1

---

풀이

수열이 주어질 때 부분 수열 중에서 수열의 합이 S가 될 때의 개수를 구해야 한다. 부분 수열은 집합에서 부분 집합을 구하는 방식과 동일하다. 수열이 {1, 2}라면 부분 수열은 {}, {1}, {2}, {1, 2}로 $2^2$개가 된다.

부분 수열의 합을 구하기 위해, 재귀 함수로 첫번째 원소부터 마지막 원소까지 탐색하면서, 다음 2가지 경우에 따라 총 합을 갱신해 나간다.

1. 현재 원소를 선택하지 않는다. -> 총합은 그대로
   recur(depth + 1, total);
2. 현재 원소를 선택한다. -> 총합 갱신
   recur(depth + 1, total + seq[depth]);

마지막 원소까지 탐색한 후 총합에 따라 카운트를 갱신한다.

static void recur(int depth, int total) {
    if (depth == N) {  //마지막 원소일 경우 리턴
        if (total == S) {
            count++;
        }
        return;
    }
    recur(depth + 1, total);  //현재 원소 포함X
    recur(depth + 1, total + seq[depth]);  //현재 원소 포함
}

전체 코드

//백준
public class Main {

    static int[] seq;
    static int N, S, count;

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());  //수열의 크기
        S = Integer.parseInt(st.nextToken());

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

        recur(0, 0);
        if (S == 0) {  //공집합은 제외
            count--;
        }
        System.out.println(count);
    }

    static void recur(int depth, int total) {
        if (depth == N) {  //마지막 원소일 경우 리턴
            if (total == S) {
                count++;
            }
            return;
        }

        recur(depth + 1, total);  //현재 원소 포함X
        recur(depth + 1, total + seq[depth]);  //현재 원소 포함
    }
}