[백준] 부분수열의 합

참고: www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 - 백트래킹 문제

 - dfs에서 찾아갈 때의 느낌과 유사하므로 잘 기억해 둘 것

 

 

import java.util.Scanner;

public class Solution {
    private static int n;
    private static int s;
    private static int[] arr = new int[30];
    private static int count = 0;

    private static void func(int cur, int sum) {
        if(cur == n) {
            if(sum == s) {
                count++;
            }
            return;
        }
        func(cur+1, sum);
        func(cur+1, sum+arr[cur]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.nextInt();
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        func(0, 0);
        if(s == 0) count--;
        System.out.println(count);

    }
}