해결 전략

: 중간에서 만나기

과정.

1. 선택하고, 선택하지 않는 비트마스킹을 생각했고,
   이때의 시간복잡도는 2의 40승이다. 1000 1000 1000 * 1000...
   -> 비트마스킹으로 불가하다.
   

2. 우리가 구하고자 하는 거는 선택한 인덱스의 값을 모두 더했을 때 s값을 구하는 것이다.
   2개의 그룹으로 나뉘어서 그룹별 부분집합을 구한 뒤,
   만들어진 2개 그룹의 부분집합을 가지고 투포인터를 진행하면 된다.

• 중간에서 만나기 알고리즘이다.
  

주석을 통해 어떻게 헤쳐나갈지에 대해서...

• 두개의 그룹으로 나누자...
  

• 연속된 것이 아니고, 합이 s가 나오는 모든 경우의 수이므로,
  정렬된 상태에서 하는 것이 효율적이다.
  -> 왜냐하면 동일값이 나오는 것도 처리해야 함.

• 아래는 그룹간에서 비트마스킹 처리한 상태에서 얻은 sum값들이다.
  

• 혹시 몰라서 동일값도 넣어주었고,

• right부분도 0에서 부터 시작하게 하기 위해서 reverse 처리함.
  

• 위 2개 그룹에서의 합을 했을 때 s값이 나오게 하면 된다....