[백준] 1182 부분집합의 합

문제보기

import java.util.*;

public class Main {
  public static int cnt = 0;
  public static int n;
  public static int m;
  public static int[] arr;

  public static void go(int idx, int sum){

    if(idx == n){ 
      if( sum == m ){
        cnt += 1;
      }
      return;
    }
	 
    // 현재 인덱스의 값을 포함하는 경우
    go(idx+1, sum + arr[idx]);
    // 현재 인덱스의 값을 포함하지 않는 경우
    go(idx+1, sum);
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();

    arr = new int[n];
    for(int i = 0 ; i < n ; i++ ){
      arr[i] = sc.nextInt();
    }
    
    go(0, 0);
    
    if( m == 0 ){ // m == 0 인 경우는 공집합까지 세어주게 되므로 1개 빼야함
      System.out.println(cnt-1);
    }else{
      System.out.println(cnt);
    }
  }
}