beingsde
Sign In
Back to all DSA patterns
Backtracking•Pattern: Backtracking•Medium

Subsets — generate all subsets (power set)

Problem Intuition & Objective

Generate all 2^n subsets of a given set.

Time ComplexityO(n × 2^n)
Optimal
Space ComplexityO(n) recursion
Memory Bounds
Optimal Algorithmic Approach

DFS backtracking with a running subset that's saved at each node.

Core Invariants & Edge Cases

  • Backtracking: at each index include or exclude the element
  • Iterative bit-mask: for each number 0 to 2^n-1, collect set bits
  • For duplicates: sort and skip equal adjacent elements after first use
Previous ProblemPermutation in string (sliding window)Next Problem Combination sum — unique combinations summing to target

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.