1.풀이 N이 40이기 때문에 완전탐색으로는 시간초과가 난다. (N=20일때 문제 1182 부분수열의 합 (sosoeasy.tistory.com/30) ) 따라서 N을 반으로 쪼개고 각각(왼쪽절반과 오른쪽 절반)이 가질 수 있는 합을 구해서 경우의 수를 구해준다. (1) 절반을 잘라서 왼쪽숫자들로 만들 수 있는 모든 숫자의 합(leftsum)을 구하고 그 개수(cnt)를 dictionary형태로 저장한다 ( leftDict[leftsum]=cnt ) (2) 오른쪽 절반에서 rightsum을 구하고, leftDict[S-rightsum]이 있으면 해당 숫자만큼을 ans에 더해준다. (3) 왼쪽의 합 만으로 S를 만드는 경우의 수, 오른쪽의 합 만으로 S를 만드는 경우의 수는 (2)에서 더해지지 않는다...