Subsets

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 1: Let’s start with a straight forward naive approach. Let’s use pass by reference and recursion.

//Approach 1:
//Runtime: 1ms
//Memory usage: 38.5MB
class Solution {
    
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> base = new ArrayList<Integer>();
        List<List<Integer>> result = new ArrayList<>();
        result.add(base);
        createSubsets(base, nums, 0, result);
        return result;
    }
    
    private void createSubsets(List<Integer> base, int[] nums, int start, List<List<Integer>> result){
        for(int i = start; i<nums.length; i++){
            List<Integer> curr = createCopy(base);
            curr.add(nums[i]);
            result.add(curr);
            createSubsets(curr, nums, i+1, result);
        }
    }
    
    private List<Integer> createCopy(List<Integer> list){
        List<Integer> copy = new ArrayList<>();
        for(Integer i : list){
            copy.add(i);
        }
        return copy;
    }
}

Clearly this approach is heavy on its usage of data structures and this slows down the computation. There is a lot of scope to improve the code.

Approach 1.1: Here is a more structured way of implementing the same logic — by adopting ideas borrowed from dynamic programming. Referring to this article, we have —

Given 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.

The code looks like —

//Approach 1.1
//Runtime: 1ms
//Memory usage: 38.4MB
class Solution {
   public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        result.add(new ArrayList());
        for(int n : nums){
            List<List<Integer>> currRes = new ArrayList();
            for(List<Integer> list : result){
                List<Integer> listCopy = new ArrayList();
                listCopy.addAll(list);
                listCopy.add(n);
                currRes.add(listCopy);
            }
            result.addAll(currRes);
        }
        return result;
    }
}

This approach, yet again does not improve on the performance, but structures the code in a better way.

Find more posts here.

Cheers & Chao!