LeetCode | 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],
    []
  ]

  分析

  有n个元素的集合的真子集有2^n个，在此基础上增加1个元素，真子集个数变成了2^(n+1)，这多出来的2^n个真子集就是在原来2^n个真子集上都添加一个新元素得到的。按照这个思路得到解法1。

  如果元素个数小于32个，还可以采用解法2的思路：把n个元素对应到n个比特位上，那么穷举真子集其实就是遍历0到2^n-1这2^n个数字的二进制表示，比特位为1表示该位对应的元素存在。

  解法1

  import java.util.ArrayList;
  import java.util.Arrays;
  
  public class Subsets {
  	public ArrayList
      
       > subsets(int[] S) {
  		Arrays.sort(S);
  		ArrayList
       
        > results = new ArrayList
        
         >(); ArrayList
         
           list = new ArrayList
          
           (); results.add(list); for (int i = 0; i < S.length; ++i) { int j = results.size(); while (j-- > 0) { list = new ArrayList
           
            (results.get(j)); list.add(S[i]); results.add(list); } } return results; } }
           
          
         
        
       
      

  解法2

  import java.util.ArrayList;
  import java.util.Arrays;
  
  public class Subsets {
  	public ArrayList
      
       > subsets(int[] S) {
  		ArrayList
       
        > results = new ArrayList
        
         >(); Arrays.sort(S); int N = S.length; for (int i = 0; i < Math.pow(2, N); ++i) { ArrayList
         
           list = new ArrayList
          
           (); for (int j = 0; j < N; ++j) { if ((i & (1 << j)) > 0) { list.add(S[j]); } } results.add(list); } return results; } }