[boj] 14225 부분수열의 합

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

public class newStudy {
    static int N;
    static int[] arr;

    static boolean[] findAns;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        //반복문 어디까지 돌아야할지 체크 - 수열의 합
        int max = 0;
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
            max += num;
        }
        //부분수열의 합 배열
        findAns = new boolean[max+1];

        //배열 오름차순 정렬
        Arrays.sort(arr);
        //부분수열 갯수가 1~N개 크기 선택
        for(int i=1; i<=N; i++){
            //시작 지점 구하기.
            for(int j=0; j<N; j++){
                List startList = new ArrayList();
                startList.add(arr[j]);
                choice(i, startList, j, new boolean[N]);
            }
        }
        //부분 수열 합 오름차순 정렬
//        Collections.sort(sumList);
        //제일 작은 자연수 찾기
//        boolean findFlag = false;
//        for(int i=1; i<=max; i++){
//            if(!sumList.contains(i)){
//                findFlag = true;
//                System.out.println(i);
//                break;
//            }
//        }
        //제일 큰 수까지 못찾았으면 다음 숫자가 나올 수 없는 가장 작은 자연수
//        if(!findFlag) System.out.println(max+1);
        //제일 작은 자연수 찾기.
        boolean findFlag = false;
        for(int i=1; i<findAns.length; i++){
            //부분수열의 배열 안에서 존재하지 않는 제일 작은 자연수를 찾았을 경우
            if(!findAns[i]) {
                System.out.println(i);
                findFlag = true;
                break;
            }
        }
        // 부분수열의 배열 안에는 모든 자연수가 존재한다면 그 다음 자연수가 제일 작은 자연수
        if(!findFlag) System.out.println(max+1);
    }

    public static void choice(int cnt, List<Integer> list, int idx, boolean[] visited){
        if(list.size()==cnt){
            //합 구해서
            int sum = 0;
            for(int tmp : list){
                sum += tmp;
            }
            //크기가 cnt의 부분수열의 합을 배열에 체크 ex) 부분 수열 합이 3이면 findAns[3] = true
            findAns[sum] = true;
            return;
        }
        for(int i=idx+1; i<N; i++){
            //방문 안한 인덱스 넣기.
            if(!visited[i]){
                visited[i] = true;
                list.add(arr[i]);
                choice(cnt, list, i, visited);
                list.remove(list.size()-1);
                visited[i] = false;
            }
        }
    }
}