C++로 풀어보는 4Sum 문제 – 합이 목표값이 되는 네 수의 조합 찾기

n개의 정수를 저장하는 배열이 있다고 가정해 봅시다. 이 배열에서 네 개의 원소 a, b, c, d를 골랐을 때 a + b + c + d = target을 만족하는 모든 고유한(quadruplet) 조합을 찾는 것이 이번 문제의 목표입니다.

예를 들어 배열이 [-1, 0, 1, 2, 0, -2]이고 목표값(target)이 0이라면, 결과는 다음과 같습니다.

[[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]

문제 해결 접근 방법

이 문제는 재귀적으로 일반화된 kSum() 함수를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 k개의 수를 더하는 문제를 k-1개의 수를 더하는 문제로 줄여 나가다가, 마지막에 두 수의 합(two sum)은 투 포인터(two pointer) 기법으로 처리하는 것입니다.

알고리즘 단계

• 실제 합 연산은 kSum(arr, start, k, target) 함수가 담당합니다. 최초에는 k 값이 4로 호출됩니다.
• 결과를 담을 배열 res를 정의합니다.
• k = 2인 경우 (투 포인터 기법):
  • left := start, right := 배열 크기 - 1로 초기화합니다.
  • 크기가 2인 임시 배열 temp를 정의합니다.
  • left < right인 동안 반복합니다:
    • arr[left] + arr[right] == target이라면:
      • temp[0] := arr[left], temp[1] := arr[right]로 설정하고 temp를 res에 삽입합니다.
      • 중복을 건너뛰기 위해 left < right이면서 인접한 값이 같으면 left를 증가시킵니다.
      • 마찬가지로 right 쪽도 인접한 값이 같으면 감소시킵니다.
      • left는 1 증가, right는 1 감소시킵니다.
    • 합이 target보다 크면 right를 1 감소시킵니다.
    • 그렇지 않으면 left를 1 증가시킵니다.
• k > 2인 경우:
  • i를 start부터 (배열 크기 - k)까지 반복합니다.
    • i > start이고 arr[i] == arr[i-1]이면 중복이므로 건너뜁니다.
    • 2차원 배열 temp := kSum(arr, i + 1, k - 1, target - arr[i])를 재귀 호출합니다.
    • temp의 각 결과 뒤에 arr[i]를 추가합니다.
    • temp의 모든 원소를 res에 복사합니다.
• res를 반환합니다.

C++ 구현 예제

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   void addAll(vector < vector <int> >& res, vector < vector <int> >& temp){
      for(int i = 0; i < temp.size(); i++)res.push_back(temp[i]);
   }
   vector<vector<int>> fourSum(vector<int>& nums, int target) {
      sort(nums.begin(), nums.end());
      return kSum(nums, 0, 4, target);
   }
   vector < vector <int> > kSum(vector <int>& arr, int start, int k, int target){
      vector < vector <int> > res;
      if(k == 2){
         int left = start;
         int right = arr.size() - 1;
         vector <int> temp(2);
         while(left < right){
            if(arr[left] + arr[right] == target){
               temp[0] = arr[left];
               temp[1] = arr[right];
               res.push_back(temp);
               while(left < right && arr[left] == arr[left + 1])left++;
               while(left < right && arr[right] == arr[right - 1])right--;
               left++;
               right--;
            }
            else if(arr[left] + arr[right] > target)right--;
            else left ++;
         }
      }
      else{
         for(int i = start; i < (int)arr.size() - k + 1; i++){
            if(i > start && arr[i] == arr[i - 1])continue;
            vector < vector <int> > temp = kSum(arr, i + 1, k - 1, target - arr[i]);
            for(int j = 0; j < temp.size(); j++){
               temp[j].push_back(arr[i]);
            }
            addAll(res, temp);
         }
      }
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,-1,0,-2,2};
   print_vector(ob.fourSum(v, 0));
}

입력

[1,0,-1,0,-2,2]
0

출력

[[1,2,-1,-2],[0,2,0,-2],[0,1,0,-1]]

정리

이 알고리즘은 먼저 배열을 정렬한 뒤, 재귀 호출을 통해 문제의 차원을 하나씩 낮추고(k → k-1), 마지막 두 수의 합은 투 포인터로 O(n) 시간에 처리합니다. 또한 정렬된 상태에서 인접한 중복 값을 건너뛰는 처리를 통해 결과에 중복 조합이 포함되지 않도록 보장합니다. 시간 복잡도는 O(n^(k-1))로, 4Sum의 경우 O(n³)입니다.