[백준 1182] 부분수열의 합

 

배열의 최대길이가 20이므로 전 구간을 완전탐색한다.

 

처음에 좀 헤맸는데 재귀를 쓰라는 힌트를 보고 풀었다.

메모이제이션 기법만 안썼지 구현방법은 dp 와 다를게 없다.

 

 

public class Main {
    
    static int n;
    static int s;
    static int a[];
    static int cnt = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        s = sc.nextInt();
        a = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        recursive(0, 0);
        System.out.println(cnt);
    }
    
    public static void recursive(int idx, int sum) {
        if(idx >= n) return;
        sum += a[idx];
        if(sum == s) cnt++;
        
        recursive(idx + 1, sum - a[idx]);
        recursive(idx + 1, sum);
    }
}