Subsets Pick Skip Recursion DSA Solution

Learning Outcome

After this lesson, you should be able to model recursion as a decision tree where every index has include and exclude choices.

Problem Statement

Given an array of distinct integers, return all possible subsets.

Input	Output	Why
`nums = [1,2,3]`	`[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]`	Each number can be either excluded or included, so 3 numbers create 8 subsets.

Brute Force Approach

Use bit masks from 0 to 2^n

1. This is valid, but it hides the transferable recursion pattern.

Optimized Approach

Backtrack with a path list. At each index, first skip the value, then include it, and copy the path at the base case.

Exact Pseudocode

answer = []
path = []
dfs(index):
  if index == n:
    answer.add(copy(path))
    return
  dfs(index + 1)
  path.add(nums[index])
  dfs(index + 1)
  path.removeLast()
dfs(0)
return answer

Reference Code

class Solution:
    def subsets(self, nums):
        answer = []
        path = []

        def dfs(index):
            if index == len(nums):
                answer.append(path[:])
                return

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

        dfs(0)
        return answer

Sample Dry Run

Step	State	Result
index 0	Skip 1 branch	Subsets without 1 start building
index 1	Skip/include 2	Both branches are explored
index 2	Skip/include 3	Base case copies paths
Finish	2^3 paths copied	8 subsets returned

Complexity

Measure	Value	Reason
Time	O(n 2^n)	There are 2^n subsets, and copying each subset can cost up to n.
Space	O(n)	The recursion path stores at most n values, excluding output storage.

Measure

Value

Reason

Time

O(n

2^n)

There are 2^n subsets, and copying each subset can cost up to n.

Space

O(n)

The recursion path stores at most n values, excluding output storage.

Edge Cases

The empty subset must be included.
Copy the path at the base case.
Input values are distinct in the standard version.

Interview Checklist

Define the choice at each index.
Backtrack by removing the included value.
Do not add the same path object directly to the answer.

FAQs

Why copy the path?

The path list keeps changing during recursion, so the answer needs a snapshot.

Why are there 2^n subsets?

Each of n values has two choices: excluded or included.

What is the core pattern?

Pick-or-skip recursion.

Subsets: Pick or Skip Recursion Pattern