Backtracking

LeetCode 78

LeetCode #78Difficulty: MediumNeetCode 150

LeetCode 78: Subsets

LeetCode

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

Problem Description

Given an integer array `nums` of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Examples:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Constraints:
  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

Core Mental Model

At index i, make a binary choice: either include nums[i] in the current subset, or exclude it. Explore, then backtrack.

Formal Loop Invariant

Invariant: At depth i, subset contains a valid prefix decision from nums[0 ... i-1].

Key Architectural Takeaway:

Backtracking explores state trees and reverts modifications upon returning from recursion.

Asymptotic Complexity Analysis

Time ComplexityO(N * 2^N)Linear scan
Space ComplexityO(N) recursion stack.Constant auxiliary

Bottleneck: Power set has exactly 2^N states.

Edge Cases & Screener Traps

  • Single element array