[백준 *Java] - 부분수열의 합(1182)

부분수열의 합

1182번: 부분수열의 합

 

문제

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

입력

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

출력

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

---

👇 접근 방식 (내 생각 정리)

'문제에서 언급한 크키가 양수인 부분수열 중' 이라는 말이 바로 이해가 안됐습니다.

문제를 보고 이해하기보단, 테스트케이스를 보고 이해를 한 게 맞는 거 같네요...

N개의 정수를 가지고 합S를 만드는 경우의 수를 찾는 문제였습니다

 

basecase 부분에서 합일 때, return 하는 방식으로 짰으며

재귀 루프에선, 나열된 배열을  중복이 되지 않게 조합으로 만들어서 합해주면 될 거 같다는 생각으로 코드를 접근했습니다.

 

하지만, 여기서 S가 0 일 때를 신경써서 처리해야할 거 같습니다.

---

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

public class Boj_1182 {
    static int N, S;
    static int[] arr;
    static int count;

    public static void backTracking(int start, int depth, int sum) {
        if (S == sum) count++;

        for (int i = start; i < N; i++) {
            backTracking(i + 1 ,  depth + 1, sum + arr[i]);
        }
    }

    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());

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

        backTracking(0, 0, 0);


        // s가 0인 경우 카운트가 생기고 시작하니 제거
        if (S == 0) count--;

        System.out.println(count);
    }
}