백준 14225 부분수열의 합

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

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

public class Main {
    private static int n;
    static int[] arr;
    static HashSet<Integer> set = new HashSet<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

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

        dfs(0, 0);
        List<Integer> list = new ArrayList<Integer>(set);
        Collections.sort(list);
        int j = 0;
        for (int i : list) {
            if (j < i) {
                break;
            }
            j += 1;
        }

        System.out.println(j);
    }

    private static void dfs(int idx, int total) {
        if (idx == n) {
            set.add(total);
            return;
        }
        dfs(idx + 1, total);
        dfs(idx + 1, total + arr[idx]);
    }
}

1. 재귀를 통해서 모든 경우의 수를 구한다
2. HashSet을 이용하여 중복값을 제거한다
3. j값과 HashSet의 값을 이용해서 비교
4. 만약 HashSet의 값이 더 크다면 j값을 출력한다.

다른사람 풀이

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

public class Main {
    private static int n;
    static int[] arr;
    static int[] ch = new int[20 * 100000 + 20];
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

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

        dfs(0, 0);
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == 0) {
                System.out.println(i);
                break;
            }
        }
    }

    private static void dfs(int idx, int total) {
        if (idx == n) {
            ch[total] = 1;
            return;
        }

        dfs(idx + 1, total);
        dfs(idx + 1, total + arr[idx]);
    }
}

재귀를 통해서 ch리스트를 만들어서 방문 했다면 표시를 해주어 확인

HashSeT을 통해서 값을 얻고 리스트화하여 정렬하고 값을 구하는 과정에서 메모리를 많이 사용하여 시간이 더걸린다