C++で解く組み合わせの合計 II(Combination Sum II)―バックトラッキングによる実装

問題概要

候補となる数値の集合(すべての要素は一意)とターゲットの数値が与えられたとき、候補の数値の合計がターゲットと一致するすべての一意な組み合わせを求めます。ただし、同じ数値を候補から複数回選ぶことはできません。

例えば、要素が [2,3,6,7,8] でターゲットが 8 の場合、出力は [[2,6],[8]] となります。

解法のアプローチ:バックトラッキング

この問題は再帰的なバックトラッキングを用いて解くのが一般的です。再帰関数 solve() を定義し、引数として現在のインデックス、配列 a、残りのターゲット値 b、現在の組み合わせを保持する配列 temp を渡します。

アルゴリズムの手順

1. 結果を格納するための空の配列 res を用意します。
2. b = 0 の場合、temp を res に追加して return します(組み合わせが見つかった状態)。
3. index が配列 a のサイズに達した場合は return します。
4. b < 0 の場合も return します(合計がターゲットを超えたため探索を打ち切り)。
5. 配列 a をソートします(重複チェックのため)。
6. i を index から 配列 a のサイズ − 1 までループします。
   • i > index かつ a[i] == a[i-1] の場合は continue でスキップ(同じ組み合わせの重複を防止)。
   • a[i] を temp に追加します。
   • solve(i + 1, a, b − a[i], temp) を再帰的に呼び出します。
   • temp の末尾要素を削除してバックトラックします。

最後に solve() を index = 0、配列 a、ターゲット b、空の配列 temp を渡して呼び出し、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:
    vector < vector <int> > res;
void solve(int idx, vector <int> &a, int b, vector <int> temp){
      if(b == 0){
         res.push_back(temp);
         return;
      }
      if(idx == a.size())return;
      if(b < 0)return;
      sort(a.begin(), a.end());
      for(int i = idx; i < a.size(); i++){
         if(i > idx && a[i] == a[i-1])continue;
         temp.push_back(a[i]);
         solve(i + 1, a, b - a[i], temp);
         temp.pop_back();
      }
   }
   vector<vector<int> > combinationSum2(vector<int> &a, int b) {
      res.clear();
      vector <int> temp;
      solve(0, a, b, temp);
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,3,6,7,8};
   print_vector(ob.combinationSum2(v, 10)) ;
}

入力

[2,3,6,7,8]
10

出力

[[2, 8],[3, 7]]

実装のポイント

重複回避の鍵となるのが、ソート後の「i > index かつ a[i] == a[i-1] の場合はスキップする」という条件です。これにより、同じ値から始まる重複した組み合わせが結果に含まれるのを防げます。

また、再帰呼び出しの後に temp の末尾要素を取り除くことで、別の候補を試すバックトラッキングが実現できます。ターゲットを超えた時点で早期に return することで、無駄な探索を削減し、計算量を抑えられる点も重要です。