• 부분집합
    • 해당 index를 선택할 지 또는 안 할지, 2가지 방향이 존재한다.
  • 시간복잡도 : $2^{20} = 1,048,576$ $~$$~$ $O(2^N)$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40



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

public class Solution {
    static int N, B;
    static int[] input;
    static int res;

    static void dfs(int idx, int sum) {
        if (idx >= N) {
            if (sum >= B) res = Math.min(res, sum);
            return;
        }
        dfs(idx+1, sum + input[idx]);
        dfs(idx+1, sum);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int testcase = Integer.parseInt(in.readLine());
        for (int tc = 1; tc <= testcase; tc++) {
            res = Integer.MAX_VALUE;

            StringTokenizer st = new StringTokenizer(in.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            input = new int[N];
            st = new StringTokenizer(in.readLine(), " ");
            for (int i = 0; i < N; i++)
                input[i] = Integer.parseInt(st.nextToken());

            dfs(0, 0);
						
            System.out.println("#" + tc + " " + (res - B));
        }
    }
}