BOJ - 부분수열의 합

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

1182번: 부분수열의 합

 

• 백트렉킹 활용 문제이다
• 문제에서 제시하는 부분 수열의 의미를 잘 파악해야 된다.
• Arr = [1,1,1,1] S = 1 인 경우 부분 수열의 개수는 [1]을 갖고 있는 4개가 된다.
• 처음에 visit 배열로 중복성 확인을 해가며 풀었는데 구지 그럴 필요가 없었던 문제였다.

 

import java.io.*;
import java.util.*;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int answer = 0;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        int[] arr = new int[N + 1];

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

        List<Integer> map = new ArrayList<>();
        dp(map, 0, arr, arr.length, S);
        System.out.println(answer);
    }

    private static void dp(List<Integer> map, int depth, int[] arr, int m, int target) {
        if (depth > m) {
            return;
        }

        int sum = map.stream().mapToInt(o -> o).sum();
        if (!map.isEmpty() && sum == target) {
            answer += 1;
            //System.out.println(map);
        }

        for (int i = depth + 1; i < arr.length; i++) {
            map.add(arr[i]);
            dp(map, i, arr, m, target);
            map.remove(map.size() - 1);
        }
    }
}