SEA3752_가능한 시험점수

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
/**
 * 점수에 대한 부분집합을 다 만들어서 HashSet에 넣어주는 방법
 * 시간초과 이유 : 원소100개에 대한 부분집합 -> 2^100...
 * 
 * */
public class Solution {
    
    static HashSet<Integer> hs;
    static int[] arr;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            
            hs = new HashSet<>();
            int N = Integer.parseInt(br.readLine().trim());
            arr = new int[N];
            int[] arr_index = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            subset(arr_index, 0, N, 0);
            System.out.println("#" + tc + " " + hs.size());
        } // end of tc
    } // end of main
 
    private static void subset(int[] arr_index, int size, int n, int index) {
        if(n == index) { // 부분 집합이 만들어 지는 경우
            int sum = 0;
            for (int i = 0; i < size; i++) {
                sum += arr[arr_index[i]];
            }
            hs.add(sum);
            return;
        }
        arr_index[size] = index;
        subset(arr_index, size+1, n, index+1);
        subset(arr_index, size, n, index+1);
        
    } // end of subset
} // end of class
 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;
/**
 * 중복제거를 위해 boolean배열 사용한 방법
 */
public class Solution {
    
 
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            
            int N = Integer.parseInt(br.readLine().trim());
            int[] arr = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
            
            // 숫자를 저장하면서 check배열의 크기를 결정하기 위해 모두 더한 값을 저장
            int sum = 0;
            for (int i = 0; i < N; i++) {
                int number = Integer.parseInt(st.nextToken());
                arr[i] = number;
                sum += number;
            }
            
            // 원소들을 모두 더한 크기로 check배열 생성
            /**
             * check배열
             * index 0 1 2 3 4 5 ....
             * value t f f f f f ....
             * 일때 숫자 2가 들어오면 check배열의 뒤에서 부터 탐색하면서 true인 곳을 찾아 index와 합한 곳의 위치를 true로 바꿔줌
             * 
             * number = 2일때 check배열
             * index 0 1 2 3 4 5 ....
             * value t f t f f f ....
             * 
             * number = 3일때 check배열
             * index 0 1 2 3 4 5 ....
             * value t f t t f t ....
             */
            boolean[] check = new boolean[sum+1];
            check[0] = true;
            for (int i = 0; i < N; i++) {
                int number = arr[i];
                for (int j = sum; j >= 0; j--) {
                    if(check[j]) {
                        check[j+number] = true;
                    }
                }
            }
            // check에서 true인 곳만 찾아서 cnt++해주면 끝
            int cnt = 0;
            for (int i = 0; i <= sum; i++) {
                if(check[i]) {
                    cnt++;
                }
            }
            System.out.println("#" + tc + " " + cnt);
        } // end of tc
    } // end of main
} // end of class