부분수열의 합

📍 문제 설명

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

14225번: 부분수열의 합

 

 

💡 접근

부분 수열의 합 중에서 제일 작은 자연수를 찾는 문제

1부터 증가시키면서 셋에 담겨있는 합인지 확인하고 존재하지 않는 값이 나올 때 멈춰주면 된다.

 

👩‍💻 코드

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

public class Main {
    static int n, m, v, e, k, r, answer, cnt, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static int[] arr, dx = {1,0,-1,0}, dy = {0,-1,0,1};
    static long[] dp;
    static int[][] board;
    static boolean[] visited;
    static ArrayList<Integer> list;
    static HashSet<Integer> set;
    static StringBuilder sb;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        set = new HashSet<>();

        T.solution(0, 0);
        answer = 1;
        while(true) {
            if(set.contains(answer)) answer++;
            else break;
        }
        System.out.println(answer);
    }

    private void solution(int L, int sum) {
        if(L == n) {
            if(sum > 0) set.add(sum);
            return;
        }
        solution(L+1, sum+arr[L]);
        solution(L+1, sum);
    }


}