My solution using bit manipulation


  • 203
    T
    class Solution {
    public:
        vector<vector<int> > subsets(vector<int> &S) {
            sort (S.begin(), S.end());
            int elem_num = S.size();
            int subset_num = pow (2, elem_num);
            vector<vector<int> > subset_set (subset_num, vector<int>());
            for (int i = 0; i < elem_num; i++)
                for (int j = 0; j < subset_num; j++)
                    if ((j >> i) & 1)
                        subset_set[j].push_back (S[i]);
            return subset_set;
        }
    };

  • 1
    L

    This confuses me at some point.
    Would you mind to add some explanation?
    That would be helpful and kind. :)


  • -9
    H

    That should fail if the input S is not sorted.
    Mine is accepted and I didn't see any testing case. I don't know if there is any unsorted testing case.


  • 95
    R

    Java codes in a similar way.

    public List<List<Integer>> subsets(int[] S) {
    	Arrays.sort(S);
    	int totalNumber = 1 << S.length;
    	List<List<Integer>> collection = new ArrayList<List<Integer>>(totalNumber);
    	for (int i=0; i<totalNumber; i++) {
    		List<Integer> set = new LinkedList<Integer>();
    		for (int j=0; j<S.length; j++) {
    			if ((i & (1<<j)) != 0) {
    				set.add(S[j]);
    			}
    		}
    		collection.add(set);
    	}
    	return collection;
    }

  • 2
    M

    Can please explain the logic of code ?

     for (int i = 0; i < elem_num; i++)
            for (int j = 0; j < subset_num; j++)
                if ((j >> i) & 1)
                    subset_set[j].push_back (S[i]);

  • 13
    J

    what if S.size() > 32?


  • 384
    L
     This is an amazing solution.Learnt a lot.Let me try to explain this to those who didn't get the logic.
    
     Number of subsets for {1 , 2 , 3 } = 2^3 .
     why ? 
    case    possible outcomes for the set of subsets
      1   ->          Take or dont take = 2 
      2   ->          Take or dont take = 2  
      3   ->          Take or dont take = 2 
    
    therefore , total = 2*2*2 = 2^3 = { { } , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }
    
    Lets assign bits to each outcome  -> First bit to 1 , Second bit to 2 and third bit to 3
    Take = 1
    Dont take = 0
     
    0) 0 0 0  -> Dont take 3 , Dont take 2 , Dont take 1 = { } 
    1) 0 0 1  -> Dont take 3 , Dont take 2 ,   take 1       =  {1 } 
    2) 0 1 0  -> Dont take 3 ,    take 2       , Dont take 1 = { 2 } 
    3) 0 1 1  -> Dont take 3 ,    take 2       ,      take 1    = { 1 , 2 } 
    4) 1 0 0  ->    take 3      , Dont take 2  , Dont take 1 = { 3 } 
    5) 1 0 1  ->    take 3      , Dont take 2  ,     take 1     = { 1 , 3 } 
    6) 1 1 0  ->    take 3      ,    take 2       , Dont take 1 = { 2 , 3 } 
    7) 1 1 1  ->    take 3     ,      take 2     ,      take 1     = { 1 , 2 , 3 } 
    
    In the above logic ,Insert S[i] only if (j>>i)&1 ==true   { j E { 0,1,2,3,4,5,6,7 }   i = ith element in the input array }
    
    element 1 is inserted only into those places where 1st bit of j is 1 
       if( j >> 0 &1 )  ==> for above above eg. this is true for sl.no.( j )= 1 , 3 , 5 , 7 
    
    element 2 is inserted only into those places where 2nd bit of j is 1 
       if( j >> 1 &1 )  == for above above eg. this is true for sl.no.( j ) = 2 , 3 , 6 , 7
    
    element 3 is inserted only into those places where 3rd bit of j is 1 
       if( j >> 2 & 1 )  == for above above eg. this is true for sl.no.( j ) = 4 , 5 , 6 , 7 
    
    Time complexity : O(n*2^n) , for every input element loop traverses the whole solution set length i.e. 2^n
    

  • 2
    L

    Take data type for j as bitset instead of int.It should solve your problem.


  • 2
    S

    The code is concise and elegant. However the run time appears not optimal compared to other solution. it's taking N*2^N. I think you can solve it by 2^N.


  • 0
    L

    Thanks for you explain, cool!, nice work.


  • 0
    C

    Learned a lot. Code is very neat.


  • 0
    N

    Actually, @thumike sorting S at the beginning.


  • 5
    E

    Amazing solution, it directly captures the intrinsic connection between power set and binary numbers.

    When forming a subset, for each element, only 2 possiblities, either it is in the subset or not in the subset, hence we have total number of possible subsets = 2^n.

    thinking each element as a bit, it's either on or off when forming the ith subset, and that's the solution!


  • 0
    Q
    int limit = Math.min(N, i + 1);
    for (int j = 0; j < limit; j++) {
    

    // add this step between two loops will reduce the time


  • 2
    S

    Do you need to sort the nums first?


  • 0
    C

    I think sort is necessary in this case, due to the fact that the original list may not be sorted while the output should be in non-descending order.


  • 0
    H

    Thank for your share!


  • 0
    S

    Nice! Elegant! Nice and elegant!


  • 0
    Y

    Thanks for the explanation!


  • 1
    F

    Thanks a lot! very good code!, Here is python version:

    def subnets(nums):
        nums.sort()
        total=2**len(nums)
        res=[]*total
    
        for i in range(total):
            res.append([])
    
        for i in range(len(nums)):
            for j in range(total):
                if ((j>>i)&1) >0:
                    res[j].append(nums[i])
        return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.