Deviopath › Python

All Subsets with Backtracking

Hard · Recursion

Backtracking builds answers step by step: choose an item, explore further, then undo the choice and try the next one. For subsets, each recursive call records the current path, then tries adding every later item.

Write subsets(nums) that returns every subset of nums (all values are distinct integers). Each subset must be sorted ascending, and the list of subsets must be sorted the way Python sorts lists ([] < [1] < [1, 2] < [1, 2, 3] < [1, 3] < [2]).

If you sort nums first and record each path before extending it, the order comes out right by itself. A list of n items has 2 ** n subsets.

Next: LRU Cache