ArrayList powerSet(ArrayList s) {
ArrayList result = new ArrayList();

if (s.size() == 1) { // base case
// return a new ArrayList containing just s
ArrayList tempAL = new ArrayList();
tempAL.add(s);
result.add(tempAL);
return result;
}
else {
Integer last = (Integer)s.get(s.size()-1); // separate the first character from the rest
ArrayList rest = new ArrayList(); // remainder of the set
rest.addAll(s);
rest.remove(rest.size()-1); // get rid off element "last"

// recursively call method on the remainder of the set
ArrayList L = new ArrayList();
L.add( powerSet(rest) ); // recursively call method on the remainder of the set

// return the set composed of the Union of
// the powerset of the set without the element (from the recursive call)
result.addAll(L);

// return the same set but
// with each element therein unioned with the element initially taken out
for(int i=0; i< L.size(); i++) {
ArrayList tmp = new ArrayList();
tmp.addAll( (ArrayList)L.get(i) );
tmp.add(last); // adding the element initially taken out
result.add(tmp);
}

return result;
}
}