# Backtracking - Subsets

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS

## Problem

Given an integer array `nums`

of **unique** elements, return *all possible* *subsets* *(the power set)*.

The solution set **must not** contain duplicate subsets. Return the solution in **any order**.

**Example 1:**

1
2

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

**Example 2:**

1
2

Input: nums = [0]
Output: [[],[0]]

## Solution

This is one of the classic backtracking algorithm. For every `index`

location, we need to run `dfs()`

twice. One using the element and another time is not using the element. Let’s look at the graph below.

Start by defining the variables. We need two of them, one for returning the final `output`

and another one for saving the `subset`

.

1
2

output = []
subset = []

Next the most important part is to identify the terminating condition, that is when to add the current `subset`

to the `output`

array. Whenever we reach the end of the tree, that is the `index`

is equal to the `len(nums)`

we know that we have reached a leaf and now need to add the `subset`

to the `output`

.

1
2
3
4

def dfs(index):
if index >= len(nums):
output.append(subset.copy())
return

Now the recursive calls.

1
2
3
4
5

subset.append(nums[index])
dfs(index + 1)
subset.pop()
dfs(index + 1)

Now call the `dfs()`

by passing `index`

as `0`

and return the `output`

.

1
2

dfs(0)
return output

### Reverse Way!

Can you now implement the reverser way? So instead of adding the `nums[index]`

value to the `subset`

and popping it later. Start without the `subset.append(nums[index])`

and add it in the second choice. Below is the code:

1
2
3
4
5
6
7
8
9
10
11
12

...
# Call dfs() without appending the nums[i]
dfs(index + 1)
# now add it and call dfs()
subset.append(nums[index])
dfs(index + 1)
# before returning still need to pop it.
subset.pop()

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def subsets(nums):
output = []
subset = []
def dfs(index):
if index >= len(nums):
output.append(subset.copy())
return
subset.append(nums[index])
dfs(index + 1)
subset.pop()
dfs(index + 1)
dfs(0)
return output