백준 1182 부분수열의 합 Java

백트래킹 문제인 부분수열의 합 문제이다.

N과 S가 주어질 때

N개의 정수로 이루어진 수열에서 S가 되는 부분 수열의 개수를 출력하면 되는 문제이다.

예제로 주어진 

5 0

-7, -3, -2, 5, 8의 경우엔

1. -3 + -2 + 5 = 0 

이 하나의 경우만 된다.

 

N의 제한이 20이기 때문에 백트래킹으로

N개의 정수로 만들 수 있는 모든 부분수열을 만들어 보면 된다.

 

주의해야 할 점은

S가 0인 경우에

아예 빈 부분집합 즉 공집합인 경우에도

백트래킹에서 조건에 맞다고 처리하고 개수를 +1 하므로

S가 0인 경우엔 개수에서 -1을 해준다.

또한

i번째 수를 더하는경우와 더하지 않는 경우를 통해

모든 부분집합을 찾아볼 것이므로

백트래킹 중간에 S와 부분집합의 합이 같다고 해서

return을 하면 안된다.

중간에 return을 해버리면 모든 부분집합의 합을 비교해볼 수 없게 되는 것이다.

i번째 수가 마지막 수 일 때 합과 S를 비교해서 정답을 찾아나간다.

 

import java.util.Scanner;
 
public class Q1182 {
    static int ans = 0;
 
    public static void backtrack(int[]a, int sum, int index, int s) {
        if(index >= a.length) {
            if(sum == s) {
                ans ++;
            }
            return;
        }
 
        backtrack(a, sum+a[index], index+1, s);
        backtrack(a, sum, index+1, s);
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int s = scan.nextInt();
        int [] a = new int[n];
 
        for(int i=0; i<n; i++)
            a[i] = scan.nextInt();
        backtrack(a, 0, 0, s);
        if(s == 0) ans--;
        System.out.println(ans);
    }
}