[알고리즘] 백준 1182 - 부분 수열의 합

문제본문

문제 해설

수열 원소의 개수 N은 1<= N <= 20이고, 크기가 양수인 부분 수열의 합으로 만들어야 하는 S는 |S| <= 1,000,000입니다.
부분 수열의 순서가 중요하지 않기 때문에 집합을 구성하는 방식을 N번에서 2번으로 줄일 수 있습니다. 그렇다면 시간복잡도는 O(2 ^ 20)이 되기 때문에 완전탐색으로도 풀 수 있습니다.

재귀호출로 해당 원소를 포함한다와 안한다로 부분 집합을 구현하고 나서 S의 값이 맞다면 경우의 수 값을 증가시키면 됩니다.

주의할 점

크기가 양수인 부분 수열이기 때문에 S가 0일 경우 공집합은 제외 해주어야 합니다.

전체 코드

import java.util.Scanner;

public class Main {
    static int answer = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int s = scanner.nextInt();

        int[] num = new int[n];

        for (int i = 0; i < n; i++) {
            num[i] = scanner.nextInt();
        }
        brute(s, 0, 0, num);
        if (s == 0) {
            answer--;
        }

        System.out.println(answer);
    }

    public static void  brute(int target, int startIndex, int sum, int[] num) {
       if (startIndex >= num.length) {
            if (sum == target) {
                answer++;
            }
        } else {

            brute(target, startIndex + 1,sum, num);
            brute(target, startIndex + 1,sum + num[startIndex], num);

        }
    }
}