Subsets

Question (LC.78)

Given a set of distinct integers, nums, return all possible subsets.

The solution set must not contain duplicate subsets. Assume input does not contain duplicates.

Example

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

Analysis

Finding all possible subsets - we need DFS for sure.

Code

Main function - pass in a reference to DFS

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

DFS Tree

private void subsetDFS(List<List<Integer>> results, 
    int[] nums, int startIndex, List<Integer> subset) {
    results.add(new ArrayList<>(subset));
    for (int i = startIndex; i < nums.length; i++) {
        subset.add(nums[i]);
        subsetDFS(results, nums, i + 1, subset);
        subset.remove(subset.size() - 1);
    }
}

This is an introduction to recursion tree and DFS tree. So we want to play around and analyze it for a bit.

What happens if we do this?

results.add(new ArrayList<>(subset));
if (startIndex == nums.length) {
     return;
}
for (int i = startIndex; i < nums.length; i++) {
    subset.add(nums[i]);
    subsetDFS(results, nums, i + 1, subset);
    subset.remove(subset.size() - 1);
}

Emmm nothing has changed because the for loop forces the DFS stops when startIndex == nums.length.
How about if we switch them?

if (startIndex == nums.length) {
     return;
}
results.add(new ArrayList<>(subset));
for (int i = startIndex; i < nums.length; i++) {
    subset.add(nums[i]);
    subsetDFS(results, nums, i + 1, subset);
    subset.remove(subset.size() - 1);
}

This will only output the last level of the recursion tree.
Now, how do we only display the second level [1,3], [2,3], [1,2]?

if (startIndex == nums.length - 1) {
    results.add(new ArrayList<>(subset));
    return;
}
for (int i = startIndex; i < nums.length; i++) {
    subset.add(nums[i]);
    subsetDFS(results, nums, i + 1, subset);
    subset.remove(subset.size() - 1);
}

ᶘ ͡°ᴥ͡°ᶅ why doesn't this work??
Well, it was trick question. [1,3], [2,3], [1,2] is when the size of the subset is 2 but is not really the second level of the recursion tree which is [1,2], [2]. So the correct way to do it is

if (subset.size() == 2) {
    results.add(new ArrayList<>(subset));
    return;
}
for (int i = startIndex; i < nums.length; i++) {
    subset.add(nums[i]);
    subsetDFS(results, nums, i + 1, subset);
    subset.remove(subset.size() - 1);
}

Time Complexity

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

To Do

first recurve vs for loop
array switch approach
why the first way is less efficient
iterative approach

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?

Code

for (int i = startIndex; i < nums.length; i++) {
    if (i > startIndex && nums[i] == nums[i-1]) {
        continue;
    }
    subset.add(nums[i]);
    subsetDFS(results, nums, i + 1, subset);
    subset.remove(subset.size() - 1);
}

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.