Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
nums = [1,2,3][[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]nums = [0][[],[0]]Unlike combinations, we add curr to results at every recursive call — this captures all subsets including the empty set. The for loop starting at start prevents duplicates by only going forward. Each element is either included or excluded, giving 2^n total paths.
Each number is either in or out, so there are 2 to the power n subsets. We can generate them as a recursion tree where every node is one subset.
Start with an empty path, and record it as a subset. From index start, add each later number, recurse, and then remove it again. Only moving forward keeps every subset unique, because 2, 1 is never built after 1, 2.
Choose, explore, then un-choose. Every node of the tree is a subset, so record it on entry.
Run the animation above on your own input, or watch the 1:19 video explanation of Subsets with a dry run and Java code.