1182 부분수열의 합

문제

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

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

코드

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

public class P_1182 {

    static int[]            info;
    static int[]            seq;
    static int              result = 0;
    static BufferedWriter   bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        seq = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        find_subseq(0, 0);

        if (info[1] == 0) result--;
        bw.write(Integer.toString(result));
        bw.flush();
    }

    public static void find_subseq(int cnt, int sum) {
        if (cnt == info[0]) {
            if (sum == info[1]) result += 1;
        }
        else {
            find_subseq(cnt + 1, sum);
            find_subseq(cnt + 1, sum + seq[cnt]);
        }
    }
}

코드 설명

백트래킹을 이용했다.

이 문제의 요점은 부분수열을 만들 건데 현재 참조하고 있는 부분의 수가 포함될 수도, 포함되지 않을 수도 있다는 것이다.

그래서 포함되는 경우와 포함되지 않는 경우를 모두 다뤄야한다.

그렇기 때문에 find_subseq 함수에서
find_subseq(cnt + 1, sum)은 해당 수가 포함되지 않는 경우를 의미하고,
find_subseq(cnt + 1, sum + seq[cnt])는 해당 수가 포함되는 경우를 의미한다.

이 두 재귀를 이용해서 각각의 수가 포함되는 경우, 포함되지 않는 경우에서 파생되는 가짓수를 모두 다룰 수 있게 된다.

cnt의 개수는 연산을 위해 다룬 수의 개수를 의미하는데 다음 수를 다룰 때마다 cnt + 1을 인자로 넘겨주기 때문에 결국 모든 수를 다루게 되면 cnt의 값은 n값이 된다.

cnt가 n이되면 인자로 넘겨받은 합이 s와 일치한지 일치하지 않은지 봐야한다.
일치하지 않을 경우는 굳이 신경쓸 필요가 없고, 일치한 경우는 전역변수로 설정한 result값을 1씩 증가시켜 주면 된다.

다만, 이 코드는 s가 0일 때 공집합일 경우에도 result가 1 카운트 되는 현상이 발생한다.
find_subseq(cnt + 1, sum)이 n만큼 진행될 경우 sum은 아무 수도 참조하지 않았으므로 0이 되어 버린다.

부분 수열은 공집합까지 확인하지 않으므로 s가 0일 때만 -1을 해 주어서 offset을 맞춰주어야 한다.