부분수열의 합

• Subset sum problem 이라는 유명한 문제로, NP-complete 임이 잘 알려져있는 문제다.
• 그래서 다항시간 알고리즘이 존재하지 않는다. exponential time에 풀려면 그냥 무식하게 모든 부분수열의 합을 다 구해보고, 그중에서 S의 갯수를 찾으면 부분수열의 갯수인 O(2^n)에 찾을 수 있다. n이 20밖에 안되므로, 이렇게 풀어도 통과하는데에는 문제가 없다.
• Meet in the middle 테크닉을 사용하면 O(2^(n/2))로 줄일 수 있다. 위키에서는 이 방법을 Horowitz and Sahni라고 소개하고 있다. 수열을 앞의 절반과 뒤의 절반으로 쪼갠 다음, 앞의 절반으로 만들수 있는 모든 부분수열의 합과, 뒤의 절반으로 만들 수 있는 모든 부분수열의 합을 각각 구해서 s1[]과 s2[]에 각각 저장한다. 이제 s1[i]+s2[j]=S가 되는 (i,j)쌍의 갯수를 찾으면 된다. 이것은 정렬 후에 투 포인터를 써도 되지만, 그냥 s2의 원소들을 딕셔너리(카운터)에 각 숫자와 등장횟수를 저장해놓고서, 모든 s1[i]에 대해서 (S - s1[i])의 갯수를 더해주는 것이 더 간단하다.

"""Solution code for "BOJ 1182. 부분수열의 합".

- Problem link: https://www.acmicpc.net/problem/1182
- Solution link: http://www.teferi.net/ps/problems/boj/1182

Tags: [MeetInTheMiddle]
"""

import collections


def main():
    N, S = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]

    first, second = [0], [0]
    for num in nums[:N // 2]:
        first.extend([num + x for x in first])
    for num in nums[N // 2:]:
        second.extend([num + x for x in second])
    second_counter = collections.Counter(second)

    answer = sum(second_counter[S - f] for f in first)
    if S == 0:
        answer -= 1
    print(answer)


if __name__ == '__main__':
    main()