[BOJ] 1182 부분수열의 합 - Java

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

1182번: 부분수열의 합

---

1. 문제

부분수열의 합을 구하는 문제이다.

2. 풀이

기본 부분수열 문제이다.

비트마스킹으로 풀어보았다.

3. 코드

package com.steady.steady_and_slowly;

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

public class Main {

    static int N, S, ans;
    static int[] arr;

    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());
        S = 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());
        }
        // 입력 끝

        for (int i=1; i< 1<<N; i++) {   //부분집합의 개수, 0: 공집합
            int sum = 0;
            for (int j=0; j<N; j++) {
                if ((i & (1<<j)) != 0) {    //존재한다
                    sum += arr[j];
                }
            }
            if (sum == S) ans++;
        }
        System.out.println(ans);
    }
}

4. 사담

기존 재귀방식 subset보다 간단한 것 같다.