0

このアルゴリズム/アプローチの実装として、次の関数を作成して、特定の文字列のパワーセット (すべてのサブセットのセット) を生成しました。

vector<string> getAllSubsets(string a, vector<string> allSubsets) 
{   
    if(a.length() == 1)
    {   
    // Base case, 
    allSubsets.push_back("");
    allSubsets.push_back(a);
    }

    else {
        vector<string> temp = getAllSubsets(a.substr(0,a.length()-1),allSubsets);
        vector<string> with_n = temp;
        vector<string> without_n = temp;
        for(int i = 0;i < temp.size()-1;i++) 
        {
            allSubsets.push_back(with_n[i] + a[a.length()-1]);
            allSubsets.push_back(without_n[i]);
        }
    }
    return allSubsets;

}

ただし、誰かが間違っているようです。呼び出しのためにサイズが増加する必要がある場合、再帰呼び出しから再帰呼び出しまでのサイズtempと静的なままです。これが起こる理由はありますか？allSubsetspush_back()

4

1 に答える 1

3

それは、オフバイワンエラーがあるためです。これはベースの隣のケースで発生するため、エントリを挿入することはありません。

最初の無効なインデックスはtemp.size()であるため、i < temp.size()常に有効なインデックスがあることを意味します。1 を引くということは、ベクトルの最後の要素が欠落していることを意味します。

常に empty であるため、パラメーターとして渡すのallSubsetsはちょっとばかげていることに注意してください。この種のアルゴリズムは、単純に 2 番目のパラメーターを必要としません。次に、重複排除を簡単かつ迅速に実行できるハッシュ セットを使用すると、より効率的になる可能性があります。

于 2015-03-25T20:48:26.893 に答える