C++で整数の約数のすべての組み合わせを出力する方法

問題概要

この記事では、整数 n が与えられたとき、その約数（因子）を掛け合わせて n になるすべての組み合わせを出力する方法を解説します。

まず、具体例を見て理解を深めましょう。

入力: 24
出力:
2 2 2 3
2 4 3
8 3
4 6
2 12

この例では、24 を複数の約数の積として表現できるパターンがすべて列挙されています。

解決アプローチ：再帰とバックトラッキング

この問題は、再帰関数を使って約数の組み合わせを順番に生成することで解決できます。見つかったすべての組み合わせは、2次元の vector（vector の vector）に格納していきます。

アルゴリズムの流れは以下の通りです。

• 探索開始位置となる約数の値と、それまでに選んだ約数の積を引数として再帰呼び出しを行う
• 積がちょうど n に等しくなった時点で、その組み合わせを結果リストに追加する
• n で割り切れる数だけを候補に加え、戻り際に要素を取り除く（バックトラッキング）ことで、さまざまな組み合わせを網羅的に探索する

C++での実装例

以下のコードは、この解法の実装例です。

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> factor_Combo;

void generateFactorCombinations(int first, int eachFactor, int n, vector<int>factor) {
    if (first > n || eachFactor > n)
        return;
    if (eachFactor == n) {
        factor_Combo.push_back(factor);
        return;
    }
    for (int i = first; i < n; i++) {
        if (i * eachFactor > n)
            break;
        if (n % i == 0) {
            factor.push_back(i);
            generateFactorCombinations(i, i * eachFactor, n, factor);
            factor.pop_back();
        }
    }
}

void printcombination() {
    for (int i = 0; i < factor_Combo.size(); i++) {
        for (int j = 0; j < factor_Combo[i].size(); j++)
            cout << factor_Combo[i][j] << "\t";
        cout << endl;
    }
}

int main() {
    int n = 24;
    vector<int> single_result_list;
    cout << "All Factor combinations of " << n << " are :\n";
    generateFactorCombinations(2, 1, n, single_result_list);
    printcombination();
    return 0;
}

実行結果

All Factor combinations of 24 are −
2 2 2 3
2 2 6
2 3 4
2 12
3 8
4 6

コードのポイント解説

• first 引数： 各再帰レベルで探索を開始する約数の値です。これにより「2 × 6」と「6 × 2」のような順序が違うだけの重複を防げます。
• eachFactor 引数： それまでに選んだ約数の積を保持します。この値が n に到達したとき、1つの組み合わせが完成したことになります。
• バックトラッキング： push_back() で約数を追加し、再帰から戻った後に pop_back() で取り除くことで、別の組み合わせの探索へスムーズに移行できます。
• 探索開始を 2 からにする理由： 1 を含めると「1 がいくつでも並んでよい」ことになり組み合わせが無限に増えるため、2 から探索を開始します。

まとめ

再帰とバックトラッキングを組み合わせることで、ある整数の約数によるすべての掛け算の組み合わせを効率よく列挙できます。計算量は約数の個数に依存するため、小〜中規模の整数に対して特に実用的な手法です。素因数分解や組み合わせ最適化の基礎としても応用範囲が広いので、ぜひマスターしておきましょう。