> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/graph-search/exhaustive-search/subsets.md).

# Subsets

## Question ([LC.78](https://leetcode.com/problems/subsets/))

> 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

```java
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]`?

```java
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

```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

```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&#x20;

```python
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

```java
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](https://leetcode.com/problems/subsets-ii/))

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.

```java
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.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/graph-search/exhaustive-search/subsets.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.