Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Hint: for a set of N distinct numbers, the total number of subsets is 2^N. The idea is to use a boolean array used[], which has the same length with S, to indicate whether a number of S at position i is selected.

Solution 1: 

01 public ArrayList<ArrayList<Integer>> subsets(int[] S) {

02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();        

03     if(S.length==0)

04         return results;

05   

06     //use a boolean array to indicate whether a number is selected

07     boolean [] used =new boolean [S.length];

08   

09     //first sort S, so that outputs are in correct order

10     Arrays.sort(S);

11     findSubsets(used, 0, S, results);

12     return results;

13 }

14 public void findSubsets(boolean [] used, int pos, int [] S, ArrayList<ArrayList<Integer>> results)

15 {

16     //reach the last position, output our selection

17     if(pos==S.length)

18     {

19         ArrayList<Integer> out =new ArrayList<Integer>();

20         for(int i=0;i<used.length;i++)

21         {

22             if(used[i])

23             {

24                 out.add(S[i]);

25             }

26         }

27         results.add(out);

28         return;

29     }

30   

31     //each position can be false or true,

32     //indicating whether the number at this position is selected or not

33     //then handle the next position

34     used[pos]=false;

35     findSubsets(used, pos+1, S, results);

36   

37     used[pos]=true;

38     findSubsets(used, pos+1, S, results);

39 }

Solution 2:

Instead of using an additional boolean array to store the information of which numbers are selected, we can use an integer to do so. In this manner, we pre-calculate how many subsets we will have in total, say, N. Then we use number 0 to N-1 to represent each subset. For example, we use 0, 1, 2, 3 to represent the subsets of 2 numbers, i.e., 00, 01, 10, 11. This is an iterative solution instead of a recursion one.

Java语言: Subsets

01 public ArrayList<ArrayList<Integer>> subsets(int[] S) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();        
03     Arrays.sort(S);              
04     //calculate total number of subsets        
05     for(int i=0;i<(1<<S.length);i++)
06     {
07         ArrayList<Integer> set=new ArrayList<Integer>();          
08         //convert this number representation into set
09         int number=i;          
10         for(int j=0;j<S.length;j++)
11         {              
12             if(number==0)
13                 break;
14             //the digit is 1, indicate the number is selected
15             if(number%2==1)
16             {
17                 set.add(S[j]);
18             }
19             //shift one bit to right, then check the next digit
20             number>>=1;
21         }
22         results.add(set);
23     }
24     return results;      
25 }