[1182] 부분수열의 합

🔗 문제 링크

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

🔍 문제 설명

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

⚠️ 제한사항

• 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)

• 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.

• 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

🗝 풀이 (언어 : Java)

조합을 만들어서 모든 케이스를 체크하는 문제이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        br.close();
        int[] numbers = new int[N];
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st2.nextToken());
        }
        solution(S, numbers);
    }

    private static void solution(int S, int[] numbers) {
        int[] count = new int[] {0};
        recursive(S, numbers, -1, 0, count);
        System.out.println((S == 0) ? count[0] - 1 : count[0]);
    }

    private static void recursive(int S, int[] numbers, int idx, int sum, int[] count) {
        if (idx == numbers.length - 1) {
            if (sum == S) { //정답을 찾은 경우, 카운트
                count[0] += 1;
            }
            return;
        }
        recursive(S, numbers, idx + 1, sum, count); //다음 위치의 숫자를 고르지 않는 경우(= 합계에 포함 X)
        recursive(S, numbers, idx + 1, sum + numbers[idx + 1], count); //다음 위치의 숫자를 고르는 경우(= 합계에 포함 O)
    }

}