How can you generate all subsets of a set using a recursive algorithm?

Generating All Subsets of a Set

In determining all subsets of a given set, the number of elements (n) plays a crucial role. An effective algorithm harnesses recursive techniques to achieve this.

Recursive Algorithm

The recursive algorithm operates on the principle that, for each element, the subsets can be partitioned into two categories: those containing the element and those excluding it. These two partitions share identical subsets otherwise.

Beginning with n=1, we have two subsets: {} (the empty set) and {1}.

For n>1, we determine the subsets of 1,...,n-1 and duplicate them. One set will have n added to each subset, while the other will remain unchanged. The union of these two sets yields the complete set of subsets.

Illustrative Example

Let's generate the subsets of {1, 2, 3, 4, 5}:

• n=1: {{} , {1}}
• n=2: Take {} , {1} and add 2. Union with {} , {1}: {{} , {1} , {2} , {1, 2}}
• n=3: Add 3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: Add 4: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , {1, 2, 3, 4}}
• n=5: Add 5: {{} , {1} , {2} , {1, 2} , {3} , {1, 3} , {2, 3} , {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , {1, 2, 3, 4}, {5} , {1, 5} , {2, 5} , {1, 2, 5} , {3, 5} , {1, 3, 5} , {2, 3, 5} , {1, 2, 3, 5}, {4, 5} , {1, 4, 5} , {2, 4, 5} , {1, 2, 4, 5} , {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4, 5}}

Thus, we arrive at all 32 subsets of {1, 2, 3, 4, 5}.

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