1 <= n <= 40
-> 시간초과 2^40
-> 반으로 쪼개서 처리한다.
[2251] 물통이 생각난다.
물통c에만 물이 가득하고 나머지a,b는 비어있다면
물의 양은 물통a = a, 물통b = b, 물통c = c-a-b로 정의할 수 있었다.
배열을 반으로 나눠서 먼저 왼쪽배열의 경우의 수 와 중복을 기록한다(a).
target을 만드는 경우의 수가 왼쪽과 오른쪽에 걸처 존재한다면,
target(c) - sum(b), 즉 a와 겹치는 경우의 수가 있을 것이다.
target이 0일 경우, 포함하거나 안하는 처리(bs(s+1, e, sum, RL))에서
0에 의미없이 1이 들어가기 때문에 이를 예외처리 한다.
let p = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n,target) = (p[0],p[1])
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dict = [Int:Int]()
let mid = n/2
var cnt = target == 0 ? -1 : 0
func bf(_ s:Int,_ e:Int,_ sum:Int,_ LR:String) {
if s == e {
switch LR {
case "L": dict[sum,default: 0] += 1
default : cnt += dict[target-sum,default: 0]
}
return
}
bf(s+1, e, sum, LR)
bf(s+1, e, sum + arr[s], LR)
}
bf(0, mid, 0, "L")
bf(mid, n, 0, "R")
print(cnt)