K개 숫자의 합을 구하는 문제.

보통 투 포인터나 이진 탐색을 응용하는 문제 중에는 N개의 주어진 숫자 중 k개의 합을 특정 숫자로 만들수 있는가? 를 묻는 문제가 자주 있다.

이런 문제를 해결하는 과정은 보통 2가지 유형으로 구분이 된다.

1. 투포인터(가운데에서 만나기)

k가 3인 경우가 이러한 경우이다.
1개의 숫자를 고정하고, 2개의 숫자를 투 포인터로 활용하여 범위 내에서 값을 조정해나가는 것이다.

이런 방식을 사용하면, N^2 의 시간복잡도로 해결이 가능하다. (바깥 루프 N, 내부 루프 N)

two-sum 문제의 응용으로 볼 수 있다.

예시 문제.
https://www.acmicpc.net/problem/3151

two-sum

2개의 숫자를 합해 특정 숫자를 만드는 문제이다. 일반적으로 배열을 오름차순 정렬하여 양 끝에서 포인터를 만들고, 두 숫자의 합이 target 값보다 커지면, 오른쪽 포인터를 줄이고 작아지면 왼쪽 포인터를 증가시킨다.

이렇게 하면 합한 값이 목표한 target으로 수렴하게 되는데 결과적으로 정렬 알고리즘의 시간복잡도인 $O(N log_2(N))$으로 해결이 가능하다.

다른 방법으로는 해시를 사용할 수 있다. 이 방법은 매우 빠르지만 힙 메모리를 많이 사용하는 부담이 있다.
우선 해시 셋을 생성한 뒤, 앞에서부터 요소의 값을 셋에 집어 넣는다.

그 후 i번째 인덱스의 값 ary[i]를 target에서 뺀 target - ary[i]가 셋에 있는지를 확인하는 것으로 해결이 가능하다.

HashSet<Integer> set = new HashSet<>();

for(int i = 0; i < n; i++) {
	// 동일한 두 숫자를 사용하면 안된다는 조건이 있을 때는
    // 이렇게 추가 전에 검사를 해야한다.
	if(set.contains(target - ary[i])) return true;
    set.add(ary[i]);
}

2. 이진탐색 또는 해시 응용

a+b+c = d
이런 값을 찾는 문제를 변형하면, d가 주어진 배열 안에 있어야 한다는 조건을 추가할 수 있다.

특정값 d가 배열에 존재하는지 여부가 상관 없다면, 위에서 보인 three-sum 문제를 응용할 수 있지만, 배열 안에 존재해야한다면 다르다.

d가 확정적으로 배열에 존재한다면 c를 이항하여
a+b = d-c 로 두고 볼 수 있다.

a, b, c, d가 같은 숫자여도 관계가 없다면, a+b의 모든 조합을 미리 계산하고 d-c가 그 안에 존재하는지를 스캔하여 답을 찾을 수 있다.

이때, 시간복잡도는 $O(N^2)$이므로 너무 크지 않은 입력에 대해서 유효하게 동작한다.

다음으론 4-sum 문제가 있다.
a+b+c+d가 특정 값이 되어야 한다면,
a+b를 먼저 계산하고 정렬한 뒤에, c+d를 계산하여 이 target - (c+d)의 값이 a+b 배열에 존재하는지 이진탐색으로 발견할 수 있다.

(또는 해시 테이블을 활용해도 된다.)

그 외의 경우

DP나 비트마스크를 활용할 수도 있다. 관련 문제를 찾으면 내용을 업데이트 하겠다.