C++でArrayList(vector)を使って文字列のすべての部分列(サブシーケンス)を出力する方法

問題概要

この記事では、与えられた文字列のすべての部分列(サブシーケンス)を出力する方法を解説します。部分列とは、元の文字列から0個以上の文字を削除することで得られる文字列のことであり、残った文字同士の相対的な順序は変更してはいけません。

まず、具体例で問題を確認しましょう。

入力: string = "xyz"
出力: x y xy z xz yz xyz

このように、元の順序を保ちながら、空でないすべての文字の組み合わせが出力されます。

解法のアプローチ

すべての部分列を求める最も基本的な方法は再帰を利用することです。各文字に対して「部分列に含める」「含めない」という2つの選択肢を順に試すことで、すべての組み合わせを網羅的に生成できます。

C++にはJavaのArrayListのようなクラスは存在しませんが、同等の機能を持つ動的配列コンテナとしてstd::vectorが用意されています。ここでは、生成した部分列をvector<string>に格納し、まとめて出力する実装を紹介します。

C++による実装例

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// すべての部分列を再帰的に生成する関数
void generateSubsequences(const string& str, const string& subSeq, vector<string>& result) {
    // ベースケース: 文字列を使い切ったら結果へ格納
    if (str.empty()) {
        if (!subSeq.empty()) {
            result.push_back(subSeq);
        }
        return;
    }

    char ch = str[0];           // 先頭の文字
    string ros = str.substr(1); // 残りの文字列

    // 現在の文字を「含めない」場合
    generateSubsequences(ros, subSeq, result);

    // 現在の文字を「含める」場合
    generateSubsequences(ros, subSeq + ch, result);
}

int main() {
    string str = "wxyz";
    vector<string> subsequences;

    generateSubsequences(str, "", subsequences);

    cout << "The subStrings are :" << endl;
    for (const auto& s : subsequences) {
        cout << s << " ";
    }
    cout << endl;

    return 0;
}

実行結果

The subStrings are :
z y yz x xz xy xyz w wz wy wyz wx wxz wxy wxyz

コードのポイント

• ベースケース: 入力文字列が空になった時点で、それまでに構築したsubSeqを結果のvectorに追加します。ここでは空文字列を除外しています。
• 再帰の分岐: 各呼び出しで先頭文字を「取る」「取らない」の2通りに分岐するため、長さnの文字列からは最大2ⁿ個の部分列が生成されます。
• vectorの活用: 即座に出力する代わりにvectorへ蓄積することで、ソートや重複除去など、後続の処理への応用が容易になります。

計算量について

長さnの文字列の部分列は最大2ⁿ個存在するため、時間計算量はO(2ⁿ × n)(各部分列の構築・格納にO(n)が必要なため)となります。空間計算量も結果を保持する関係上、同様にO(2ⁿ × n)です。組み合わせの数が指数的に増加するため、この手法は文字列が比較的短い場合に適しています。