HwangHub

🤔 Intuition아이디어를 떠올리기 어려워 결국 다른 이의 풀이를 참고했다. 요지는, 전체 부분수열을 부분집합 알고리즘으로 탐색하게 되면 (2 ^ 40) 정도라서 시간을 초과하지만, 이를 절반씩 쪼개서 부분집합을 구하면 (2 * 2 ^ 20) 이라서 시간이 터지지 않는다. 따라서 이를 절반으로 쪼개어 부분수열의 합을 구한 뒤, 한쪽 절반의 부분수열의 합을 기준으로 다른 반쪽의 부분수열의 합과 더한 값이 S가 될 때의 개수를 세주면 된다.🔎 Algorithm & Complexity * @algorithm backtracking (powerset)* @time O(2^N/2) : 976 ms* @memory O(N) : 96908 KB 👨🏻‍💻 Logic오른쪽 반 쪽의 부분수열의 합을 먼저 구..