再帰的アプローチを使用して、n 個の要素を含むセットのすべての可能なサブセットを見つけるにはどうすればよいでしょうか?

セットのすべてのサブセットの検索

コンピューター サイエンスでは、指定されたセットのすべてのサブセットを見つけることは古典的な問題です。次のような疑問が生じます:

問題:

n 個の要素を持つセットのすべての可能なサブセットを決定するにはどうすればよいですか?

解決策:

この問題に対する直接的なアプローチは再帰にあります。この概念は、次の考えを中心に展開しています。

• n=1 の場合、サブセットは {{}, {1}}
• n>1 の場合、次のサブセットを分割できます。 1,...,n-1 を 2 つのグループに分けます: n を含むグループと n を含まないグループ。これらのグループを結合すると、1,...,n のサブセットが得られます。

例:

n=5 を考えます。

1. 1、...、4 のサブセットを見つけます: {{}、{1}、{2}、 {3}、{4}、{1, 2}、{1, 3}、{1, 4}、{2, 3}、{2, 4}、{3, 4}、{1, 2, 3 }, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}
2. 作成コピーして各サブセットに 5 を追加します: {{5}、{1, 5}、{2, 5}、{3, 5}、{4, 5}、{1, 2, 5}、{1, 3 、5}、{1、4、5}、{2、3、5}、{2、4、5}、{3、4、5}、{1、2、3、5}、 {1, 2, 4, 5}、{1, 3, 4, 5}、{2, 3, 4, 5}、{1, 2, 3, 4, 5}}
3. 元のセットと変更されたセットの結合: {{}、{1}、{2}、{3}、{4}、{5}、{1, 2}、{1, 3}、{1、 4}、{1, 5}、{2, 3}、{2, 4}、{2, 5}、{3, 4}、{3, 5}、{4, 5}、{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}、{1, 2, 3, 4}、{1, 2, 3, 5}、{ 1、2、4、5}、{1、3、4、5}、{2、3、4、5}、{1、2、3、4、 5}}

C 実装:

#include <vector>

using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    if (nums.empty()) return {{}};

    vector<vector<int>> prev = subsets(vector<int>(nums.begin(), nums.end() - 1));
    vector<vector<int>> curr;

    for (auto& subset : prev) {
        curr.push_back(subset);
        subset.push_back(nums.back());
        curr.push_back(subset);
    }

    return curr;
}

以上が再帰的アプローチを使用して、n 個の要素を含むセットのすべての可能なサブセットを見つけるにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。