Subsets

Question (LC.78)

Given a set of integers, return all possible subsets of the given set.

The solution set cannot contain duplicate subsets. How large is the set? less than 15 elements Does the set contain duplicates? nope Positive and negative? both

Example

I: [1,2,3]
O: [ [],
     [1], [2], [3], 
     [1,2], [1,3],
     [2,3],
     [1,2,3]
   ]

Exhaustive Search (prefix tree)

Starting from an empty set and recording all the states to enumerate the set.

Define Recursion
genSubsets(List<List<Integer>> results, int[] nums, List<Integer> subset, int startIndex)
startIndex is a starting node for this depth first search
Add all susbets starting with startIndex with subset as prefix to results

Recursive Calls
for i from startIndex to n-1
    genSubsets(results, nums, new subset.add(i), i+1)

Base Case
if startIndex = n: results.add(new subset)

Code

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    // edge check
    if (nums == null) return results;
    // sorting nums is not needed in this case
    Arrays.sort(nums);
    // recursive helper
    List<Integer> subset = new ArrayList<>();
    genSubsets(results, nums, subset, 0);
    // return results
    return results;
}

// traverse the recrusion tree
private void genSubsets(List<List<Integer>> results, 
                        int[] nums, 
                        List<Integer> subset,
                        int startIndex) {          
    // preorder traversal (log)
    results.add(new ArrayList<>(subset));
    // dfs
    for (int i = startIndex; i < nums.length; i++) {
        subset.add(nums[i]);
        genSubsets(results, nums, subset, i+1);
        subset.remove(subset.size() - 1);
    }
}

How do we only display the second level [1,3], [2,3], [1,2]?

if (subset.size() == 2) {
    results.add(new ArrayList<>(subset));
    return;
}

Exhaustive Search (decision tree)

We can either include or disinclude an element.

Define recrusion:
genSubsets will either put in or put out the current element and record the leaf state to results
genSubsets(List<List<Integer>> results, int[] nums, int curEle, List<Integer> subset)

Recursive calls:
genSubsets(results, nums, curEle + 1, subset.notadd(curEle))
genSubsets(results, nums, curEle + 1, subset.add(curEle))

Base case:
if (curEle == nums.length)
    results.add(new subset)
    return

Code

Java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null) return results;
    List<Integer> subset = new ArrayList<>();
    genSubsets(results, nums, 0, subset);
    return results;
}

private void genSubsets(List<List<Integer>> results, 
                        int[] nums, 
                        int curEle, 
                        List<Integer> subset) {
    // base
    if (curEle == nums.length) {
        results.add(new ArrayList<>(subset));
        return;
    }
    // recursive calls
    genSubsets(results, nums, curEle + 1, subset);
    subset.add(nums[curEle]);
    genSubsets(results, nums, curEle + 1, subset);
    subset.remove(subset.size() - 1);
}

Python

def subsets(self, nums: List[int]) -> List[List[int]]:
    # kick off a helper function
    results = []
    self.subsets_helper(results, nums, [], 0)
    return results
    
# helper function def subsets_helper(self, nums, )
def subsets_helper(self, results, nums, curList, curIndex):
    # base case
    if curIndex == len(nums):
        results.append(curList)
        return
    # left branch (out)
    self.subsets_helper(results, nums, curList, curIndex + 1)
    # right branch (in)
    self.subsets_helper(results, nums, curList + [nums[curIndex]], curIndex + 1)

Do it iteratively

def subsets(self, nums: List[int]) -> List[List[int]]:
    results = [[]]
    for num in nums:
        temp_results = results.copy()
        for result in temp_results:
            subset = result + [num]
            results.append(subset)
    return results

Binary Number

We can see how each element is either included or disinclined in a subset. This is kind of binary property to make us wonder if there's a solution with bit manipulation. We can observe the formulation from this example.

ex. [1,2,3]
000
001
010
011
100
101
111

Code

public List<List<Integer>> subsets2(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    int n = nums.length;
    for (int sub = 0; sub < (1 << n); sub++) { // Math.pow(2,n)
        List<Integer> subset = new ArrayList<>();
        for (int index = 0; index < n; index++) {
            if ((sub & (1 << index)) > 0) {
                subset.add(nums[index]);
            }
        }
        results.add(new ArrayList<>(subset));
    }
    return results;
}

Time Complexity

#subproblems * time/subproblem = 2^n * O(n) = O(n*2^n)

Follow Up (LC.90)

What if the input has duplicates?

Example

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

Analysis

The easiest and space-costly way would be having a hashset to store all the subsets that are visited. But can we prune some repetitive subtrees?

Prune Decision Tree

Now we need to sort the input.

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> results = new ArrayList<>();
    if (nums == null) return results;
    // sorting is needed
    Arrays.sort(nums);
    List<Integer> subset = new ArrayList<>();
    genSubsets(results, nums, 0, true, subset);
    return results;
}

private void genSubsets(List<List<Integer>> results, 
                        int[] nums, 
                        int curEle,
                        boolean used,
                        List<Integer> subset) {
    if (curEle == nums.length) {
        results.add(new ArrayList<>(subset));
        return;
    }
    genSubsets(results, nums, curEle + 1, false, subset);
    // element nums[curEle-1] is the same as nums[curEle]
    // but nums[curEle-1] is not included in the subset
    // we are repeating a subtree same as before
    if (!used && nums[curEle] == nums[curEle-1]) {
        return;
    }
    subset.add(nums[curEle]);
    genSubsets(results, nums, curEle + 1, true, subset);
    subset.remove(subset.size() - 1);
}

Prune Prefix Tree

So the key is i > startIndex && nums[i] == nums[i-1]. Since we already sorted nums in this case, we can skip duplicates by checking current_element == previous_element. Also i > startIndex guarantees that this is not the first iteration in the current loop.