Given a set S, how do you find the non-empty power set of S ? By non-empty, I mean all the subsets except the null set. I find this useful when I was building a keyboard manager that needed to figure out all the unique key combinations, each can be mapped to a different function. For example, pressing c has a different meaning than ctrl-c, alt-c, alt-ctrl-c, etc. Here are two implementations in OO javascript.

To run the demo script, simply invoke demo('calcPn') which takes O(2^n) time, or demo('calcPnByTim') which takes O(n*2^n) time.

<script>
/**
 * Non-emtpy Power Set Calculation.
 *
 * @author Hanson Char
 * @author Tim Lavers
 */
/**
 * PSet Class Definition.
 */
function PSet() {}
/**
 * Factory method to return a singleton instance of PSet.
 */
PSet.getInstance = function() {
   return PSet['inst'] == null 
     ? PSet.inst = new PSet() 
   : PSet.inst
}
/**
 * Calculate Pn, given Sn.
 *
 * Pn is an array representing the non-empty power set of the elements 
 * of an input array Sn, where n can be an arbitrary positive integer
 * representing the input array length.
 * The resultant elements of Pn can be in any order.  
 * 
 * Examples:
 * 
 * S1 = [E1]
 * S2 = [E1, E2]
 * S3 = [E1, E2, E3]
 * ...
 * Sn = [E1, E2, ..., En]
 *
 * P1 = [E1]
 * P2 = [E1, E2, E1E2]
 * P3 = [E1, E2, E3, E1E2, E1E3, E2E3, E1E2E3]
 * ...
 * Pn = [E1, E2, ..., En, E1E2, E1E3, ..., E1En, ... E1E2E3...En]
 * 
 * Formula:
 * 
 * Pn = Pn-1 x En + En + Pn-1
 *
 * Note this specific routine maintains the internal order 
 * of the components of each composite element in Pn as the same as 
 * the order of the elements of Sn.
 * For example, if S2 is [E1, E2], 
 * then one valid composite element in P2 is E1E2, but not E2E1.
 *
 * Takes O(2^n).
 */
PSet.prototype.calcPn = function(sa) {
    var pa = []

    for (var i=sa.length-1; i > -1; i--) {
        var e = sa[i]
        e = typeof e == "string" ? e : (e+"")

        for (var j=pa.length-1; j > -1; j--) 
            pa[pa.length] = e + pa[j]
        pa[pa.length] = e
    }
    return pa
}
/**
 * Thanks to Tim Lavers.  Here is an alternative solution.
 * Tim pointed out that Pn is equivalent to the 2^(n-1) - 1 non-empty subsets of Sn. 
 * So for each number 1 to 2^(n-1), use the base2 representation of that number 
 * as a bit vector that determines which elements are included.
 *
 * Takes O(n*2^n).
 */
PSet.prototype.calcPnByTim = function(sa) {
    var max = Math.pow(2, sa.length)
    var ta = []

    for (var i=1; i < max; i++) {
        var e = ""
        var j=0

        for (var k=i; k > 0; k = k >>> 1) {
            if (k & 1)
                e += sa[j]
            j++
        }
        ta[ta.length] = e
    }
    return ta
}
/** 
 * Demo function. 
 */
function demo(methodName) {
    var inst = PSet.getInstance()
    var a = []
    var i=0

    for (; i < 9; i++) {
        a[a.length] = String.fromCharCode(65+i)
        var func = eval("inst."+methodName)
        var ta = func(a)
        var ip1 = i+1
        if (!confirm("S"+ip1+":["+a+"]\nT"+ip1+":["+ta+"]"))
            break
    }
    if (i == 9)
        alert("That's it.\nAnything more than 9 elements may take too long to run.")
}
</script>

Update on 2Apr06: See Comprehending the Problem by Paul Brown.
Update on 24Feb07: An elegant recursive Java solution originated from Justin Sadowski:

public class PowerSet {
    void run(String[] sa) {
        f(sa, 0, "");
    }
    
    void f(String[] a, int idx, String s) {
        if (idx >= a.length)
            return;
        System.out.println(s+a[idx]);
        f(a, idx+1, s);
        f(a, idx+1, s+a[idx]);
    }
    
    public static void main(String[] args) {
        String[] sa = {"a", "b", "c"};
        new PowerSet().run(sa);
    }
}