Matsushita's Blog

Write a method to return all subsets of a set

Problem

Write a method to return all subsets of a set

Solution

This problem can be solve by choosing each element or not. For example we given an array = {1, 2, 3}. First, we do the two patterns that we select 1 or not. By this operation, we get two lists : {} and {1}. Second we do the two patterns that we select 2 or not as well. we also get the lists: {}, {1}, {2}, {1, 2}.

Recursive Approach

This idea can be formed by recursive function.

Bit Manipulation Approach

In bit manipulation case, the digit of bit corresponds to the index of the array and the flag corresponds to that the element is composed or not.