Generate Power set for a given set

17 Sep 2016

Power Set

Power set is a set of all subsets of a provided set

For example:

Consider a given set {a, b, c}, then the power set of this will contain following subsets

{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}

An easy way to solve this is to generate the sets based on the index. The index of the inner recursions should be greater than the outer 1.

using System;

namespace Powerset
{
    public class Program
    {
        static void Main(string[] args)
        {
            char[] set = new char[] { 'a', 'b', 'c' };
            PowerSet powerset = new PowerSet(set);
            for (int i = 0; i < set.Length; i++)
                powerset.Generate(i, set[i] + "");
        }
    }

    class PowerSet
    {
        char[] set;
        public PowerSet(char[] s)
        {
            set = s;
        }

        public void Generate(int idx, string combination)
        {
            Console.WriteLine(combination);
            for (int i = idx + 1; i < set.Length; i++)
            {
                Generate(i, combination + set[i]);
            }
        }
    }
}

Sample Output:

a
ab
abc
ac
b
bc
c
Press any key to continue . . .