Subsets Cont…

Question: Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

You may view the full question here.

Approach 2: We just tried a straight forward approach in our previous post. Now, after a little digging on the internet, this particular approach mentioned here blew my mind. Not necessarily because of the efficiency, but, simply for the idea itself — the binary representation of all the numbers starting from 0 to nCr indicated whether the number in that index was present or not (0 — number not present, 1 — number is present). The article here, has a representation of this approach for a list of four elements.

The code looks like this —

//Approach 2:
//Runtime: 1ms
//Memory usage: 38.4MB
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length; 
        List<List<Integer>> result = new ArrayList<>();  
        for (int i = 0; i < (1<<n); i++) 
        { 
            List<Integer> curr = new ArrayList(); 
  
            for (int j = 0; j < n; j++) 
  
                if ((i & (1 << j)) > 0) 
                    curr.add(nums[j]); 
  
            result.add(curr); 
        }
        return result;
    } 
}

Clearly, there is not much improvement in the performance yet.

Find more posts here.

Cheers & Chao!