boj 1208: 부분집합의 합2

문제의 크기가 클 경우에는 문제를 절반으로 나누어서 문제를 푼 후 두 개를 합치는 방식을 이용한다.

 

배열의 크기가 N인 집합이 있을 때 부분집합의 합이 M이 나오는 갯수를 찾는 문제이다.

이 문제의 경우는 N<=40이고 모든 부분 집합을 만들면 2^40가지가 나오므로 모든 경우의 수를 파악할 수 없다.

 

따라서 문제의 크기를 절반으로 나누어서 한쪽 절반과 다른쪽 절반에서 각각 푼 다음에 문제를 합쳐서 풀도록 한다.

먼저 절반에서 구한 모든 값들을 list에 넣고 left list의 값과 right list의 값의 합이 s인 가짓수를 찾는다.

 

부분집합의 크기는 양수이므로 둘 다 0인 경우는 마지막에 빼준다.

 

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

public class Main {
	public static long ans = 0;
	public static int arr[];
	public static int n, s;
	public static ArrayList<Integer> left, right;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		s = in.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		left = new ArrayList<Integer>();
		right = new ArrayList<Integer>();

		findAllSums(0, 0, n / 2, left);
		findAllSums(0, n / 2, n, right);

		Collections.sort(left);
		Collections.sort(right);
		int leftIndex = 0;
		int rightIndex = right.size() - 1;
		while (leftIndex < left.size() && rightIndex >= 0) {
			int leftSum = left.get(leftIndex);
			int rightSum = right.get(rightIndex);

			if (leftSum + rightSum == s) {
				long leftSame = 0;
				while (leftIndex < left.size() && left.get(leftIndex) == leftSum) {
					leftIndex++;
					leftSame++;
				}
				long rightSame = 0;
				while (rightIndex >= 0 && right.get(rightIndex) == rightSum) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum < s) {
				// 찾으려고 하는 수는 더 크기 때문에 left를 오른쪽으로 한 칸 움직여준다.
				leftIndex++;
			} else {
				// 마찬가지로 rightIndex 한칸 왼쪽으로 움직여준다.
				rightIndex--;
			}
		}

		if (s == 0) {
			ans -= 1;
		}

		System.out.println(ans);
	}

	public static void findAllSums(int sum, int index, int end, ArrayList<Integer> list) {
		if (index == end) {
			list.add(sum);
			return;
		}

		findAllSums(sum + arr[index], index + 1, end, list);
		findAllSums(sum, index + 1, end, list);
	}
}