[ BOJ ][JAVA][1182] 부분수열의 합

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	35057	16142	10218	44.161%

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

코드

조합 풀이

// 연속된 부분합 -> 투포인터
// 연속되지 않은 부분합 -> 조합 or dfs (지금 위치를 선택하느냐 마느냐)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class p1182 {
    static int n, s, cnt;
    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());
        s = Integer.parseInt(st.nextToken());

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

        boolean visit[] = new boolean[n];
        cnt = 0;
        for (int i = 1; i <= n; i++) {
            comb(arr, visit, 0, n, i);
        }
        System.out.println(cnt);
    }

    static void comb(int[] arr, boolean[] visit, int start, int n, int depth) {
        if (depth == 0) {
            if (getSum(arr, visit, n)) {
                cnt++;
            }
        }

        for (int i = start; i < n; i++) {
            visit[i] = true;
            comb(arr, visit, i + 1, n, depth - 1);
            visit[i] = false;
        }
    }

    static boolean getSum(int[] arr, boolean[] visit, int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (visit[i]) {
                sum += arr[i];
            }
        }
        if (sum == s) return true;
        return false;
    }
}

dfs 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    static int s, n;
    static int[] inputSubset;
    static int count;
    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());
        s = Integer.parseInt(st.nextToken());
        count = 0;
        inputSubset = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < n ; i++){
            inputSubset[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0,0);
        // count 합이 0인 경우 공집합도 포함되므로 그 수를 하나 빼주고 출력
        if (s == 0) {
            count--;
        }
        System.out.println(count);
    }
    public static void dfs (int index, int sum){
        // dfs로 돌며 누적시키다가 index를 끝까지 탐색했을 때
        if (index == n) {
            // 지금까지의 총합이 목표값과 같을 때
            if (sum == s) {
                count++;
            }
            return;
        }
        // 현재 index 의 값을 선택하지 않는다.
        dfs(index + 1, sum);
        // 현재 index 의 값을 선택한다.
        dfs(index + 1, sum + inputSubset[index]);
    }
}