如何使用遞歸方法找到包含 n 個元素的集合的所有可能子集？

查找集合的所有子集

在計算機科學中，查找給定集合的所有子集是一個經典問題。問題如下：

問題：

如何決定包含 n 個元素的集合的所有可能子集？

解：

解決這個問題的一個直接方法是遞歸。這個概念圍繞著這樣的想法：

• 對於n=1，子集是{{}, {1}}
• 對於n>1，我們可以分割子集1 ,...,n-1 分為兩組：包含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中文網其他相關文章！