[Java] BaekJoon 1182. 부분수열의 합(실버2) (부분집합)(DFS)

문제출처: https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

문제이해

 

목표

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

풀이

브루토 포스로 부분집합의 모든 케이스(2^n)를 구해서 부분수열의 합이 S가 나오는 경우를 찾는다.

 

주의 

단, S가 0일때 모든 값을 false로 처리하여 아예 값이 없는 부분집합의 경우도 체크하기 때문에, 이런 케이스를 제외하기 위해서 진짜 부분집합의 경우인지 확인하기 위해 check 처리해준다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.System.in;

public class 부분수열의합 {
    private static int N, S;
    private static boolean[] visited;
    private static int answer;
    private static int[] intArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        answer = 0;
        visited = new boolean[N];
        String[] strArr = br.readLine().split(" ");
        intArr = new int[N];
        for (int i = 0; i < N; i++) {
            intArr[i] = Integer.parseInt(strArr[i]);
        }

        getSubset(0);
        System.out.println(answer);
    }

    static private void getSubset(int now){
        if (now == N) {
            int sum = 0;
            boolean check = false;
            for (int i = 0; i < N; i++) {
                if(visited[i]){
                    sum += intArr[i];
                    check = true;
                }
            }
            if (sum == S && check) {
                answer++;
            }
            return;
        }

        visited[now] = true;
        getSubset(now + 1);

        visited[now] = false;
        getSubset(now + 1);

    }

}