[알고리즘] 백준 > #1182. 부분수열의 합

문제링크

백준 #1182. 부분수열의 합

풀이방법

가지치기도 할 수 없는 완전탐색 문제입니다! N의 최대값이 20이기 때문에 완탐으로 문제를 해결해도 되겠죠~? dfs를 사용해 모든 케이스를 탐색했습니다. 매번 sum이라는 부분수열의 합 값을 전달해 sum == s를 만족하면 카운트하는 방식입니다.

코드

import java.util.*;
public class BOJ1182 {

    private static int n;
    private static int s;

    private static int[] array;

    private static int count = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        s = sc.nextInt();

        array = new int[n];
        for (int i = 0; i < n; i++) array[i] = sc.nextInt();

        dfs(0, 0);

        System.out.print(count);
    }

    private static void dfs(int index, int sum) {
        if ((index != 0) && (sum == s)) count++;

        for (int i = index; i < n; i++) {
            sum += array[i];
            dfs(i + 1, sum);
            sum -= array[i];
        }
    }
}