Medium

Subsets

083

Return all subsets of nums, sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    3
  ]
}

Output
[
  [],
  [
    1
  ],
  [
    1,
    2
  ],
  [
    1,
    2,
    3
  ],
  [
    1,
    3
  ],
  [
    2
  ],
  [
    2,
    3
  ],
  [
    3
  ]
]

FUNCTION SHAPE

nums: intArray→intMatrix

SOLUTION NOTE

Recursive Thinking:

Subsets of [1,2] = (1 + subsets of [2]) and (nothing + subsets of [2]).
Subsets of [2] = {[], [2]}
Subsets of [1,2] = (1 + {[], [2]}) and ({[], [2]}) = {[1], [1,2], [], [2]}.

Keep this recursive thinking in mind to understand correctness. Don't just mindlessly apply the template.

Reveal reference solution +

pythonREFERENCE

def subsets(self, nums: List[int]) -> List[List[int]]:
    res = []
    subset = []

    def backtrack(i):
        if i == len(nums):
            res.append(subset.copy())
        else:
            # use nums[i]
            subset.append(nums[i])
            backtrack(i+1)
            subset.pop()

            # do not use nums[i]
            backtrack(i+1)

    backtrack(0)
    return res

TimeO(n*2^n)

SpaceO(n*2^n)

Open on LeetCode ↗