Backtracking is DFS over decisions. For subsets the decision at each element is simply "take it or leave it", which makes this the cleanest introduction to the pattern.
Given a list of distinct integers nums, return all possible subsets (the power set). The subsets and the numbers inside each subset may be in any order, but there must be no duplicate subsets.
Examples
Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Input: nums = [0]
Output: [[], [0]]
Constraints
0 <= len(nums) <= 10, all values distinct- Target: O(n * 2^n) time (you cannot do better: that is the size of the output)
Goals
- Apply the choose / explore / un-choose backtracking template
- Generate every subset by deciding, for each element, whether to include it
- Copy the current path when recording a result instead of storing a reference to it