C++で解く4Sum問題：和がtargetとなる4つ組をすべて見つけるアルゴリズム

問題の概要

数値の配列が与えられ、そこに n 個の整数が格納されているとします。この中から4つの要素 a、b、c、d を選び、a + b + c + d = target を満たす組み合わせをすべて見つけたいと思います。ただし、重複する組は除外し、「一意な」4つ組のみを求めます。

たとえば、配列が [-1, 0, 1, 2, 0, -2]、target が 0 の場合、結果は [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]] となります。

解法の手順

この問題は、Two Sum でおなじみの「ソート＋双方向ポインタ（two-pointer）」の手法を再帰的に一般化した kSum() 関数で解きます。最初は k = 4 で呼び出し、k が 2 になった段階で左右のポインタを動かしながらペアを探索します。

• 実際の合計計算は kSum() 関数で行います。引数は配列、開始インデックス 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 かつ arr[left] = arr[left + 1] の間、left を1つ進めます（重複の除外）。
      • left < right かつ arr[right] = arr[right − 1] の間、right を1つ戻します（重複の除外）。
      • left を1増やし、right を1減らします。
    • arr[left] + arr[right] > 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]) を取得します。
    • j を 0 から temp のサイズまで動かし、各 temp[j] の末尾に 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]]

計算量について

まず配列をソートするため O(n log n) のコストがかかります。その後の kSum の再帰では、k = 4 の場合、各段階で候補を1つずつ固定しながら絞り込んでいくため、全体の時間計算量は O(n³) 程度になります。ベースケースで two-pointer 技法を使うことで、単純な総当たり（O(n⁴)）よりも効率的に解けるのがポイントです。