Subsets

Generate all subsets using backtracking and bit manipulation.

5 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Backtracking Approach

For each element, decide to include or exclude. Recurse to next index. When index reaches n, add current subset to result.

Gosubsets-backtracking.go

22 linesLn 1, Col 1Go

At each step, add current element, recurse, then remove (backtrack). Start from different indices to avoid duplicates. Generates all 2^n subsets.

Each subset corresponds to a bitmask of length n. 0 to 2^n-1 covers all subsets. Bit i set = include nums[i].

Gosubsets-with-bit-manipulation.go

17 linesLn 1, Col 1Go

Iterate all bitmasks 0 to 2^n-1. For each mask, check bits. Simple but less efficient for large n due to bit operations.

Start with empty subset. For each number, create new subsets by appending it to all existing subsets.

Gosubsets-iterative.go

14 linesLn 1, Col 1Go

Build incrementally. For each num, double the subsets by adding num to each existing subset. Clean and efficient.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.