접근 세상에나 중간에서 만나기라는 알고리즘이 있다는 것이 신기하다. 부분수열의 합은 고등학생 때 부분집합의 갯수를 구하는 공식을 떠올려보면 이해하기 쉽다. 고등학생 때 전체 집합의 원소의 갯수가 $ N $ 개라면, 부분집합의 갯수는 $ 2^N $이 되었다. 그런 이유는 공집합에 원소마다 [넣기 / 안넣기] 2가지의 선택권밖에 없었기에, $ 2 * 2 * ... * 2 = 2^N $으로 도출될 수 있는 것이다. 여기선 최악의 경우를 생각해보면, $ O(2^{40}) $의 시간복잡도가 나오게 된다. 중간에서 만나기는 이분 탐색과 분할 정복의 형태와 비슷하다. 이분 탐색은 매 탐색마다 $ N / 2 $ 를 수행해서 시간 복잡도가 log 단위로 나오는 반면, 중간에서 만나기는 처음 한번 $ N / 2 $ 수행하..