[백준] 1182번 부분수열의 합

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

1182번: 부분수열의 합

 

• 다른 dfs와 달리 for문을 사용할 필요 없음
• 해당 원소를 포함한 부분수열의 합과 해당 원소를 포함하지 않은 부분수열의 합을 따로 구해야 함
• 정수의 합이 0일 때는 공집합도 포함하므로 count에서 1을 빼준다.

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static int n;
    public static int num;
    public static int[] arr;
    public static int count = 0;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        num = Integer.parseInt(st.nextToken()); 
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0,0);

        if(num == 0) {
        	System.out.println(count-1);
        } else {
        	System.out.println(count);
        }
    }

    public static void dfs(int depth, int sum) {
        if(depth == n) {
            if(num == sum) {
            	count++;
            }
            return;
        }
        dfs(depth + 1, sum + arr[depth]);
        dfs(depth + 1, sum);
    }

}