How can you find all possible subsets of a set with n elements using a recursive approach?

Finding All Subsets of a Set

In computer science, finding all subsets of a given set is a classic problem. The question arises as follows:

Problem:

How to determine all possible subsets of a set with n elements?

Solution:

A straightforward approach to this problem lies in recursion. The concept revolves around the idea that:

• For n=1, the subsets are {{}, {1}}
• For n>1, we can divide the subsets of 1,...,n-1 into two groups: those containing n and those not containing n. Combining these groups yields the subsets for 1,...,n.

Example:

Consider n=5.

1. Find the subsets of 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. Create a copy and add 5 to each subset: {{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. Take the union of the original and modified sets: {{}, {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 Implementation:

#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;
}

The above is the detailed content of How can you find all possible subsets of a set with n elements using a recursive approach?. For more information, please follow other related articles on the PHP Chinese website!