문제

이해

주어진 수열에서 전체 합이 S가 되는 부분 수열의 개수를 출력하면 된다.

접근

문제를 풀 때 부분 수열이 정확히 무엇인지 몰랐다.

수열은 수의 순서가 있기 때문에 부분 수열은 기존 수열에서 순서를 유지한 채로 연속된 수열인지 알았다.

그래서 처음에는 누적합을 이용해 문제를 풀었었다. 누적합의 투 포인터를 통해서 부분 수열 (오해한) 을 만들고 S인 경우를 카운트 했다.

하지만 잘못 생각했기에 당연히 오답이었고 찾아보니 부분 수열은 수열의 원소를 뽑아서 새로 만드는 수열이었다. (순서는 상관없다..)

따라서, 문제를 백트래킹으로 풀이하였다.

수열의 첫 원소부터 뽑고 다음 재귀에서 두 번째 원소를 뽑고...

이를 반복하여 수열의 모든 경우를 조사하고 S와 비교한 뒤 카운트 하면 된다.

기존의 백트래킹에서는 visited를 두어서 분기마다 계산할 때 참조했는데 이 문제는 원소의 개수와 상관없이 합을 구하기 때문에 필요없다. 단순히 뽑을 때마다 합을 재귀로 전달하면 되는 것이다.

다음 재귀에서 뽑은 수를 이전 합에 합하고 S와 계속 비교하면 되는 것이다.

수열의 순서와 관계없이 합을 같기 때문에 중복된 경우를 제거하기 위해서 이전에 뽑은 수 다음 위치부터 뽑도록 작성하였다.

코드

package java_baekjoon;

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

public class prob1182 {
    static int N;
    static int S;
    static int[] arr;
    static int cnt = 0;

    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());
        }

        back_tracking(-1, 0);

        System.out.println(cnt);
    }

    static void back_tracking(int prev, int sum) {
        if (prev == N - 1) {
            return;
        }

        for (int i = prev + 1; i < N; i++) {
            if (sum + arr[i] == S) {
                cnt++;
            }
            back_tracking(i, sum + arr[i]);
        }
    }
}

결과