Subsets
Module 16 · Recursion & Backtracking
Problem
Given an integer array nums of unique elements, return all
possible subsets (the power set). The solution set must not contain
duplicate subsets, and the order of subsets does not matter.
Examples
Example 1
nums = [1,2,3]Output[[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]Example 2
nums = [0]Output[[], [0]]Constraints
1 ≤ n ≤ 10 · all elements distinct · values in ±10. (Note the tiny n — a strong hint the intended answer is exponential and that's expected, not a failure.)
Attempt it first
This is the smallest, cleanest backtracking template there is — the one worth burning into muscle memory, because Permutations, Combination Sum, and Palindrome Partitioning are all variations on it. Before reading on, try to answer one question on paper: at each element, what is the choice? If you can name the choice, the tree — and the code — follows almost mechanically. Try to write it fully with the choose/explore/ unchoose skeleton from the concept lesson.