C++で組み合わせをすべて生成する方法【バックトラッキング解説】

問題概要

2つの整数 n と k が与えられたとき、1 から n までの数字の中から k 個を選んで作れるすべての組み合わせを求めます。
例えば、n = 4、k = 2 の場合、答えは [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] となります。

解法の考え方：バックトラッキング

この種の問題は、バックトラッキング(探索の巻き戻し)と呼ばれる手法で効率的に解くことができます。再帰関数を使って候補の数字を一つずつ選びながら組み合わせを構築し、条件を満たした時点で結果を保存していきます。

アルゴリズムの手順

• 再帰関数 solve() を用意します。引数は n、k、現在の組み合わせを保持する一時配列 temp、開始位置 start(start の初期値は 1)です。
• temp のサイズが k に達したら、temp を結果格納用の res 配列に追加して再帰を抜けます。
• i を start から n まで順に処理します。
  • temp に i を追加する
  • solve(n, k, temp, i + 1) を再帰的に呼び出す
  • temp の末尾から要素を削除する(バックトラック)
• solve(n, k, [](空の配列)) の形で最初の呼び出しを行います。
• 最後に res を返します。

再帰呼び出し時に start を「i + 1」に設定するのがポイントです。これにより、同じ数字の重複や [2,1] のような順序違いの重複を自然に防ぐことができます。

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 n, int k, vector <int> temp, int start = 1){
       if(temp.size() == k){
          res.push_back(temp);
          return;
       }
       for(int i = start; i <= n; i++){
          temp.push_back(i);
          solve(n, k, temp, i + 1);
          temp.pop_back();
       }
    }
    vector<vector<int> > combine(int n, int k) {
       res.clear();
       vector <int> temp;
       solve(n ,k, temp);
       return res;
    }
};
main(){
    Solution ob;
    print_vector(ob.combine(5,3));
}

入力

5
3

出力

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

計算量について

n 個から k 個を選ぶ組み合わせの総数は、二項係数 C(n, k) = n! / (k! × (n−k)!) で表されます。そのため、時間計算量は O(C(n, k) × k)、空間計算量も同様に O(C(n, k) × k) となります。n や k が大きくなると組み合わせの総数は急激に増加するため、実用上は n が 20 程度までの入力を目安にするとよいでしょう。