LeetCode - Subsets (Java)

Given a set of distinct integers, S, return all possible subsets.
Note: 1) Elements in a subset must be in non-descending order. 2) The solution set must not contain duplicate subsets.

For example, given S = [1,2,3], the method returns:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Iterative VersionGiven a set S of n distinct integers, there is a relation between Sn and Sn-1. The subset of Sn-1 is the union of {subset of Sn-1} and {each element in Sn-1 + one more element}. Therefore, a Java solution can be quickly formalized.

public ArrayList<ArrayList<Integer>> subsets(int[] S) { if (S == null) return null; Arrays.sort(S);  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();   for (int i = 0; i < S.length; i++) { ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();   //get sets that are already in result temp.addAll(result); //add S[i] to existing sets for (ArrayList<Integer> a : temp) { a.add(S[i]); } //add S[i] only as a set temp.add(new ArrayList<Integer>(single)); result.addAll(temp); }  //add empty set result.add(new ArrayList<Integer>()); return result; }

Code from http://www.cnblogs.com/TenosDoIt/p/3451902.html
可以根据二进制的思想，比如对于3个元素的集合，000表示一个元素都不选择，001表示选择第一个元素，101表示选择第一个和第三个元素...。因此如果集合大小为n，我们只需要让一个整数从0逐渐增加到2^n-1, 每个整数的二进制形式可以表示一个集合。如果用整数的二进制表示集合，这个算法有个限制，最大能表示集合元素的个数为64（unsigned long long）。如果使用bitmap，然后模拟二进制的加1操作，则对集合大小就没有限制。刚好这一题集合的大小不超过64
vector<vector<int> > subsets(vector<int> &S) {
    int len = S.size();
    sort(S.begin(), S.end());
    vector<vector<int> > res(1);//开始加入一个空集  
     unsigned long long bit = 1, bitmax = (1<<len);
     vector<int> tmpres;
     while(bit < bitmax)
     {
         tmpres.clear();  
         unsigned long long curBit = bit;
         for(int i = 0; i < len; i++)//依次检测前len个二进制位
         {
             if(curBit & 1)
                 tmpres.push_back(S[i]);
             curBit >>= 1;
         }
         res.push_back(tmpres);
         bit++;
     }
     return res;
 }
Code from http://blog.csdn.net/u011095253/article/details/9158397
每当我们添加了一个元素，都是一个新的子集。那么我们怎么保证不会出现重复集合呢。我们引入一个int pos用来记录此子集的起点在哪，比如当pos = 1的时候就是从第二个元素往后循环添加元素（0 base）,每次当此层用了第i个元素，那么下一层需要传入下一个元素的位置i+1 除此之外，当循环结束要返回上一层dfs的时候我们需要把这一层刚添加元素删去。
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
       ArrayList<Integer> tmp = new ArrayList<Integer>();
       Arrays.sort(S);
       res.add(tmp);
       dfs(res,tmp,S,0);
       return res;
    }
   
    public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, int[] S, int pos){
        for(int i=pos; i<=S.length-1;i++){
            tmp.add(S[i]);
            res.add(new ArrayList<Integer>(tmp));
            dfs(res,tmp,S,i+1);
            tmp.remove(tmp.size()-1);
        }
    }
Also refer to http://www.cnblogs.com/TenosDoIt/p/3451902.html
http://www.binglu.me/subsets-leetcode/
Read full article from LeetCode – Subsets (Java)