You get an array nums of distinct integers. Return all of its subsets.
A subset is any choice of some of the numbers. It can hold none of them (the empty subset) or all of them.
Inside each subset, keep the numbers in their order in nums.
The order of the subsets matters. Decide about one number at a time, and leave it out before you take it. So all subsets without nums[0] come first, then all subsets with it. Within each group, the subsets without nums[1] come first. Then the same goes for nums[2], and so on.
The empty subset is always first. The whole of nums is always last.
Example 1:
Input: nums = [4,8,6] Output: [[],[6],[8],[8,6],[4],[4,6],[4,8],[4,8,6]] Explanation: The first four subsets leave out 4. The last four take 4. In each half, the first two leave out 8. In each pair, the one without 6 comes first. Inside a subset, 8 stays before 6, as in nums.
Example 2:
Input: nums = [7] Output: [[],[7]] Explanation: One number gives two subsets: without it, then with it.
Example 3:
Input: nums = [2,-5] Output: [[],[-5],[2],[2,-5]] Explanation: The two subsets without 2 come first.
Constraints:
numsholds 1 to 10 numbers.- Each number is between -10 and 10.
- No number appears twice.
Note:
The tutorial uses backtracking. Walk through nums one index at a time, keeping the numbers taken so far in a list current. At index i, first skip nums[i]: go on to index i + 1 with current as it is. Then take it: add it to current, go on to index i + 1, and remove it again. When the index reaches the end of nums, every number has been skipped or taken: save a copy of current. Trying skip before take gives exactly the order above. It is the same choice as when you generate binary strings: a subset is a string of n bits, 0 for skip and 1 for take, and the subsets come out in the order of those strings.
There are 2n subsets and copying one takes up to n steps, so the time is O(n · 2n). Besides the answer, the extra space is O(n): the subset being built and one call per index.
Free plan: 30 tutor messages. PRO is unlimited.
