This article explains how to find all subsets of a given set of items, without using recursion. A set contains 2^N subsets, where N is the number or count of items in the set. The subsets are found using binary patterns (decimal to binary) of all the numbers in between 0 and (2^N - 1).

The technique explained here is implemented in C# and Silverlight and a live demonstration is available below with full source code.

Finding Subsets Demo in Silverlight

The techniques explained are illustrated in this demo. The source code of the demo is available for download below.

Itemset and ItemsetCollection

Two simple helper classes namely Itemset and ItemsetCollection are created. An Itemset is just a list of strings; and the ItemsetCollection is list of itemsets. These classes improve the readability and helps to easily understand the source code.

These classes are defined as follows.

public class Itemset : List<string>
{
}

public class ItemsetCollection : List<Itemset>
{
}

Creating and initializing an Itemset is very similar to the initialization of a string array.

Itemset i1 = new Itemset() { "1", "2", "3", "4", "5" };

Finding Subsets without Recursion

There will be 2^N subsets for a given set, where N is the cardinality (number of items) of that set. For example, there will be 2⁵ = 32 subsets for the set {1, 2, 3, 4, 5}. The binary representation of each number 'i' in the range 0 to (2^N - 1) is used to find the corresponding i^th subset.

Each '1' in the binary representation indicates an item in that position. For example, the binary representation of number 5 is 00101 which in turn represents the subset {3, 5} of the set {1, 2, 3, 4, 5}.

public static ItemsetCollection FindAllSubsets(Itemset itemset)
{
    ItemsetCollection allSubsets = new ItemsetCollection();

    int subsetCount = (int)Math.Pow(2, itemset.Count);
    for (int i = 0; i < subsetCount; i++)
    {
        Itemset subset = new Itemset();
        for (int bitIndex = 0; bitIndex < itemset.Count; bitIndex++)
        {
            if (GetBit(i, bitIndex) == 1)
            {
                subset.Add(itemset[bitIndex]);
            }
        }

        allSubsets.Add(subset);
    }

    return (allSubsets);
}

The GetBit() function is used to find a bit in the binary representation of the corresponding decimal number.

public static int GetBit(int value, int position)
{
    int bit = value & (int)Math.Pow(2, position);
    return (bit > 0 ? 1 : 0);
}