LogoKode$word
Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation
Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

Learn how to solve the Subsets problem using recursion, backtracking, loops, and bit manipulation. Includes Java code, intuition, and complexity analysis.

7 views
0
0
Github icon
Listen to articleAudio version

Introduction

The Subsets problem (LeetCode 78) is one of the most fundamental and frequently asked questions in coding interviews. It introduces the concept of generating a power set, which is a core idea in recursion, backtracking, and combinatorics.

Mastering this problem helps in solving a wide range of advanced problems like combinations, permutations, and decision-based recursion.

In this article, we will explore:

  1. Intuition behind subsets
  2. Recursive (backtracking) approach
  3. Iterative (loop-based) approach
  4. Bit manipulation approach
  5. Time and space complexity analysis

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

Key Points

  1. Each element can either be included or excluded
  2. No duplicate subsets
  3. Return subsets in any order

Examples

Example 1

Input:

nums = [1, 2, 3]

Output:

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

Example 2

Input:

nums = [0]

Output:

[[], [0]]

Key Insight

For each element, there are two choices:

Include it OR Exclude it

So total subsets:

2^n

This makes it a binary decision tree problem, very similar to:

  1. Permutation with Spaces
  2. Binary choices recursion
  3. Backtracking problems

Approach 1: Recursion + Backtracking (Most Important)

Intuition

At each index:

  1. Skip the element
  2. Include the element

Build subsets step by step and backtrack.

Java Code (With Explanation)

import java.util.*;

class Solution {
List<List<Integer>> liss = new ArrayList<>();

void solve(int[] an, int ind, List<Integer> lis) {

// Base case: reached end → one subset formed
if (ind == an.length) {
liss.add(new ArrayList<>(lis)); // store copy
return;
}

// Choice 1: Do NOT include current element
solve(an, ind + 1, lis);

// Choice 2: Include current element
lis.add(an[ind]);

solve(an, ind + 1, lis);

// Backtrack: remove last added element
lis.remove(lis.size() - 1);
}

public List<List<Integer>> subsets(int[] nums) {
List<Integer> lis = new ArrayList<>();
solve(nums, 0, lis);
return liss;
}
}

Dry Run (nums = [1,2])

Start: []
→ skip 1 → []
→ skip 2 → []
→ take 2 → [2]
→ take 1 → [1]
→ skip 2 → [1]
→ take 2 → [1,2]

Final Output:

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

Approach 2: Iterative (Loop-Based)

Intuition

Start with an empty subset:

[ [] ]

For each element:

  1. Add it to all existing subsets

Code

import java.util.*;

class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());

for (int num : nums) {
int size = result.size();

for (int i = 0; i < size; i++) {
List<Integer> temp = new ArrayList<>(result.get(i));
temp.add(num);
result.add(temp);
}
}

return result;
}
}

How It Works

For [1,2,3]:

Start: [[]]

Add 1 → [[], [1]]
Add 2 → [[], [1], [2], [1,2]]
Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Approach 3: Bit Manipulation

Intuition

Each subset can be represented using a binary number:

For n = 3:

000 → []
001 → [1]
010 → [2]
011 → [1,2]
...

Code

import java.util.*;

class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
int total = 1 << n; // 2^n

for (int i = 0; i < total; i++) {
List<Integer> subset = new ArrayList<>();

for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
subset.add(nums[j]);
}
}

result.add(subset);
}

return result;
}
}

Complexity Analysis

ApproachTime ComplexitySpace Complexity
RecursionO(2^n)O(n) stack
IterativeO(2^n)O(2^n)
Bit ManipulationO(2^n)O(2^n)

Why All Approaches Are O(2ⁿ)

Because:

  1. Total subsets = 2ⁿ
  2. Each subset takes up to O(n) to construct

When to Use Which Approach

  1. Recursion / Backtracking → Best for interviews (easy to explain)
  2. Iterative → Clean and beginner-friendly
  3. Bit Manipulation → Best for optimization & advanced understanding

Key Takeaways

  1. Subsets = power set problem
  2. Every element → 2 choices
  3. Think in terms of decision trees
  4. Backtracking = build + undo (add/remove)

Common Interview Variations

  1. Subsets with duplicates
  2. Combination sum
  3. Permutations
  4. K-sized subsets

Conclusion

The Subsets problem is a foundational DSA concept that appears across many interview questions. Understanding all approaches—especially recursion and iterative expansion—gives a strong base for solving complex backtracking problems.

If you master this pattern, you unlock a whole category of problems in recursion and combinatorics.

Frequently Asked Questions (FAQs)

1. Why are there 2ⁿ subsets?

Because each element has 2 choices: include or exclude.

2. Which approach is best for interviews?

Recursion + backtracking is the most preferred.

3. Is bit manipulation important?

Yes, it helps in optimizing and understanding binary patterns.

Related Articles

Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG

Permutation with Spaces Explained Using Recursion & Decision Tree | Java Solution GFG

Master the Permutation with Spaces problem using recursion and decision trees. Includes Java code with comments and step-by-step explanation.

Read Article
Recursion in Java - Complete Guide With Examples and Practice Problems

Recursion in Java - Complete Guide With Examples and Practice Problems

Learn recursion in Java from scratch. Includes how recursion works, base case, recursive case, types of recursion, dry runs, time & space complexity, and top LeetCode problems with solutions.

Read Article
Intersection of Two Arrays II

Intersection of Two Arrays II

Leetcode question 350

Read Article
All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

Learn how to generate all subsequences of a string using recursion, backtracking, and bit manipulation. Includes Java code and lexicographical sorting.

Read Article
Ai Assistant Kas
Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation | Kode$word