Subsets

One of the two basic templates of depth first search.

Definition

• Ordered sets of parent set
• Elements in subsets should be continuous

Example

If S = [1,2,3], its subsets is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Logical Steps

1. Create a recursive helper function, start at a particular position in input as starting point.
2. Recursively add element after position pointer into list (in a loop), and add lists into results.
3. Backtrack to remove last element in previous list
4. Move position cursor forward in next loop iteration for adding new elements into list.

Core Code Template

// Definition: nums, rst, list, pos
public void helper(nums, rst, list, pos) {
    // base condition:
    rst.add(new ArrayList<Integer>(list));

    // loop through all elements after pos to construct a list
    for (int i=pos; i<num.length; i++) {
        // add curr element into list
        list.add(num.get(i));

        // recur call helper, with pos = i+1
        helper(nums, rst, list, i+1);

        // backtrack, remove last element from list
        // and add in a different element next time
        list.remove(list.size()-1);
    }
}

Common Mistakes

1. When adding list into results, directly add list object into result will create empty entries in result. Need to create a new Array List object for list.
2. In helper function, will need a loop to go through all elements after start position, and call helper(nums, rst, list, i+1). If goes with no loop and helper(nums, rst, list, pos+1) directly, no new element can fill in to create new lists.

Follow Up: decuplication

There are duplicate numbers coming from input set, return all subsets. Each subset cannot have duplicate elements, but can contain different elements with the same value If S = [1,2,2], the subsets are:

[
  [2],
  [1],
  [1,2,2],
  [2,2],  // the two 2's here are different elemt with same value
  [1,2],
  []
]

Logical Steps: deduplication

1. After backtrack, we need to make sure the element added into list (nums[i]) is not the previous element.
2. Sort input numbers to put all duplicate numbers together
3. Take only the first occurrence of duplicate numbers, since number position only appears in pos once, and only being taken when i=pos, all duplicate after i=pos are skipped.

Code Implementation: deduplicate

for (int i = pos; i<nums.length; i++) {
    /**
    * take first occurrence of duplicate numbers only
    * (when first occurrence was at pos)
    */
    if (i != pos && nums.get(i) == nums.get(i-1))
        continue;

    list.add(nums.get(i));
    helper(nums, rst, list, i+1);

    //backtrack
    list.remove(list.size()-1);
}