The idea is similar to bit manipulation, but I used a recursive fashion.

If (n-1) has a subset list SS = {S1, S2, ... Sm}, n's subset should like this. The first half is still SS, and the second half is adding nth element to each items in SS. The result is combine {S1, S2, ... Sm} with {{S1,nth}, {S2,nth}, ... {Sm,nth}}

```
public void helper(List<List<Integer>> lists, int val) {
int sz = lists.size();
for(int i = 0; i < sz; i++) {
List<Integer> tmp = new ArrayList<Integer>(lists.get(i));
tmp.add(val);
lists.add(tmp);
}
}
public List<List<Integer>> subsets(int[] S) {
if(S == null) { return null; }
Arrays.sort(S);
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>()); //the seed
for(int s : S) {
helper(res, s);
}
return res;
}
```