CareerCup

string power_set(string s)
{
       string p="{";
       unsigned int i,l,n;
       l=s.length();
       n=pow(2.0,double(l));
       for(i=0;i<n;i++){
                unsigned int x=i;
                string set="{";
                int j=0;
                while(x){
                      if(x&1==1)
                                set=set+s[j];
                       x=x>>1;
                       j++;
                }
       
                set=set+"}";
                p=p+" "+set;
       }
       p=p+"}";
       return p;
}

it accept string of form AB as argument and return string of form {{}{A},{B},{A,B}}

We can do this using the number of bits equal to 1 of a number. If S has N elements and t = 0, we can loop to t = (1 << N) - 1 and at every step we check on which positions in t the bits are 1.Using the position, we show the element which is on that position in the set.For example:
S = {a,b}
t = 0 the bits are 00. We output {}
t = 1 the bits are 01. we output {b}
t = 2 the bits are 10. we output {a}
t = 3 the bits are 11. we output {a,b}
t = 4 > (1 << 2) - 1 . we stop

public static ArrayList<String> subset(String s)
{
	ArrayList<String> a=new ArrayList<String>();
	if(s.length()==0||s==null)
		return null;	
	if(s.length()==1)
	{
		a.add("");
		a.add(s);
		return a;
	}
	char c=s.charAt(0);	
	ArrayList<String> a2=subset(s.substring(1,s.length()));	
	for(String s2:a2)
	{
		a.add(s2);
		a.add(c+s2);
	}	
	return a;
}

void backtrack( int[] set, boolean[] solution, int k ) {
		if ( isSolution( solution, k ) ) {
			processSolution( set, solution );
		} else {
			boolean[] candidates = constructCandidates();
			for ( boolean candidate : candidates ) {
				makeMove( solution, candidate, k );
				backtrack( set, solution, k + 1 );
				unmakeMove( solution, candidate, k );
			}
		}
	}

	boolean isSolution( boolean[] solution, int k ) {
		return solution.length == k;
	}

	void processSolution( int[] set, boolean[] solution ) {
		System.out.print( "{ " );
		for ( int i = 0; i < solution.length; i++ )
			if ( solution[i] )
				System.out.print( set[i] + " " );
		System.out.println( " }" );
	}

	boolean[] constructCandidates() {
		boolean[] result = new boolean[2];
		result[0] = false;
		result[1] = true;
		return result;
	}

	void makeMove( boolean[] solution, boolean move, int k ) {
		solution[k] = move;
	}

	void unmakeMove( boolean[] solution, boolean move, int k ) {
	}

Simple recursion will do trick. Something like:

void Generate(T[] elements, int n, string end)
{
    if (n < 0)
    {
        Console.WriteLine(" " + end);
        return;
    }
    string newend = elements[n].ToString() + ", " + end;
    Generate(elements, n - 1, end);
    Generate(elements, n - 1, newend);
}

You start with calling Generate(array, array.Length - 1, ""

Little fancier version of the above produces the following output:

S = {a, b, c, d}
{}
{a}
{b}
{a, b}
{c}
{a, c}
{b, c}
{a, b, c}
{d}
{a, d}
{b, d}
{a, b, d}
{c, d}
{a, c, d}
{b, c, d}
{a, b, c, d}

S = {1, 2, 3}
{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}

And here is the complete program. The only tricky part is handling the first and last elements correctly.

using System;

namespace PowerSet
{
    class Program
    {
        static void Main(string[] args)
        {
            PSGenerator<char> psgChar = new PSGenerator<char>("abcd".ToCharArray());
            psgChar.GeneratePS();
            PSGenerator<int> psgInt = new PSGenerator<int>(new int[]{1, 2, 3});
            psgInt.GeneratePS();
            Console.ReadKey();
        }
    }
    class PSGenerator<T>
    {
        public PSGenerator(T[] elementArray)
        {
            elements = elementArray;
        }
        public void GeneratePS()
        {
            PrintSet();
            Generate(elements.Length - 1, "}");
        }
        void Generate(int n, string end)
        {
            if (n < 0)
            {
                Console.WriteLine("{" + end);
                return;
            }
            string newend;
            if (end == "}")
                newend = elements[n].ToString() + end;
            else
                newend = elements[n].ToString() + ", " + end;
            Generate(n - 1, end);
            Generate(n - 1, newend);
        }
        void PrintSet()
        {
            Console.WriteLine();
            Console.Write("S = {");
            if (elements.Length > 0)
            {
                Console.Write("{0}", elements[0]);
                for (int i = 1; i < elements.Length; i++)
                    Console.Write(", {0}", elements[i]);
            }
            Console.WriteLine("}");
        }
        private T[] elements;
    }
}

#include<stdio.h>

int p[3]={0,0,0};
char s[]={'a','b','c'};

void toBinary(int n)
{

int i=0;
while(n!=0)
{
p[i]= n%2;
n=n/2;
i++;
}

printf("{");
for(i=0;i<3;i++)
{
if(p[i]==1)
{

printf("%c ",s[i]);
}
}
printf("}, ");

}

void main()
{

//int p[3]={0,0,0}; // p will contail a binary 3 digit number.
//n=3, take all integers from 0 to (2^n - 1). i.e 0 to(8-1) i.e 0 to 7.


int a[]={0,1,2,3,4,5,6,7};
int i;

for(i=0;i<8;i++)
toBinary(a[i]);

}

def power_set(s):
    if len(s) == 0: return [[]]
    ps_1 = power_set(s[1:])
    ps = []
    for ss in ps_1:
        ps.append(ss)
        ps.append(ss+[s[0]])
    return ps

<script type="text/javascript">
alert("god");
</script>