C++での組み合わせ合計III(Combination Sum III)の解き方

問題概要

1から9までの数字のみを使用して、合計がnになるk個の数字の組み合わせをすべて生成することを考えます。各組み合わせは一意な数字の集合でなければならず、使用する数字はすべて正の整数、さらに解の中に同じ組み合わせが重複して含まれていてはいけません。

たとえば k = 3、n = 9 の場合、条件を満たす組み合わせは次の3通りになります。

[[1,2,6], [1,3,5], [2,3,4]]

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

この問題は、再帰を用いたバックトラッキング(探索の巻き戻し)によって効率的に解くことができます。全体の手順は以下の通りです。

• solveメソッドの作成: 再帰的に呼び出されるsolveメソッドを定義します。引数はk、n、現在の候補を保持する配列temp、探索開始位置startで、startの初期値は1です。
• nが0になったときの処理: この時点でtempのサイズがkと一致していれば、その組み合わせを結果resに追加して終了します。
• 候補の探索: iをstartからmin(9, n)まで順に試します。
  • tempにiを追加する
  • solve(k, n − i, temp, i + 1)を再帰呼び出しする
  • tempの末尾要素を削除して(バックトラック)、次の候補を試す
• メイン処理: 空のベクトルtempを用意し、solve(k, n, temp)を呼び出した後、resを返します。

再帰呼び出しのたびに開始位置を「i + 1」へ進めることで、同じ数字の再利用や、[1,2]と[2,1]のような並び順が違うだけの重複を自然に排除できるのが、このアルゴリズムの重要なポイントです。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > 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 k, int n, vector <int> temp, int start = 1){
       if(n == 0){
          if(temp.size() == k){
             res.push_back(temp);
          }
          return;
       }
       for(int i = start ; i <= min(9, n); i++){
          temp.push_back(i);
          solve(k, n - i, temp, i + 1);
          temp.pop_back();
       }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
       res.clear();
       vector <int> temp;
       solve(k, n, temp);
       return res;
    }
};
main(){
    Solution ob;
    print_vector(ob.combinationSum3(2, 9));
}

入力

2
9

出力

[[1, 8],[2, 7],[3, 6],[4, 5]]

上記の出力は k = 2、n = 9 で呼び出した場合の結果です。冒頭の例のように k = 3、n = 9 で呼び出せば、[[1,2,6], [1,3,5], [2,3,4]] が得られます。

計算量について

候補となる数字は1〜9の9個しかないため、探索空間は最大でもC(9, k)通りと非常に小さく、このシンプルなバックトラッキングの実装でも実用上十分な速度で動作します。