JAVA)1182번 부분수열의 합 - 브루트포스, 비트마스크

starmk95 2020. 8. 12. 16:55
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] num = new int[n];
        for (int i=0;i<n;i++) {
            num[i] = sc.nextInt();
        }
        // 비트마스크 - 브루트포스
        // 만들 수 있는 부분 집합들의 경우의 수들을 정수로 표현했음 (공집합 제외)
        // 1부터 2^n까지
        int cnt = 0; // 부분 수열의 합이 같은 경우의 수를 세기 위한 변수

        for (int i=1;i<(1<<n);i++) { // 만들 수 있는 모든 부분 집합들에 대해 반복
            int sum = 0;
            for (int j=0;j<n;j++) {
                if((i&(1<<j)) != 0) { // 정수로 표현한 부분 집합 i에 j가 들어있다면
                    sum += num[j];
                }
            }
            if (sum == s) { // 해당 부분집합 i에 들어있는 모든 정수들을 더한 값이 s와 같으면
                cnt+=1;
            }
        }

        System.out.println(cnt);
    }
}