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

 

 

 

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

1182번: 부분수열의 합

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    
	static int[] check;
	
	static int S;
	
	static int cnt;
	
	static int N;
	
	static List<Integer> li = new ArrayList<>();
	
	static int[] arr;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
    	
		N = sc.nextInt();
		S = sc.nextInt();
		
    	arr = new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		check = new int[N];
		
		DFS(0);
		System.out.println(cnt);
		
	}
	
	static void DFS(int L) {
		if(N==L) {
			li.clear();
			
			for(int i=0; i<N; i++) {
				if(check[i]==1) li.add(arr[i]);
			}
			if(li.size()!=0 && li.stream().reduce(0, Integer::sum)==S) cnt++;
			
			return;
		}
		
		check[L] = 1;
		DFS(L+1);
		check[L] = 0;
		DFS(L+1);
		
	}
}