Given an array of distinct numbers, return all possible subsets. The answer must not contain duplicate subsets.
DSA Animator › DSA Revision › Backtracking › Subsets
Remember: choose, explore, then un-choose. Every node of the tree is a subset, so record it on entry. The video solves Subsets (LeetCode 78, Medium) with the Backtracking pattern from the Backtracking topic, and you can replay every step in the interactive Subsets animation.
Given an array of distinct numbers, return all possible subsets. The answer must not contain duplicate subsets.
For 1, 2, 3, there are 8 subsets, from the empty set up to 1, 2, 3.
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.
Record the empty set, then add 1 to get 1. Add 2 to get 1, 2, then add 3 to get 1, 2, 3. Backtrack by removing 3 and then 2, and add 3 to get 1, 3. Backtrack to the empty set and add 2, giving 2, then 2, 3. Finally add 3 alone, which completes all 8 subsets.
In code, the helper first adds a copy of the current path to the result. Then a loop from start to n adds a number, recurses with i plus 1, and removes it. There are 2 to the n subsets, each up to n long, so it's O of n times 2 to the n.
Remember: choose, explore, then un-choose. Every node of the tree is a subset, so record it on entry.