Recursion and Backtracking Generating every choice
318. Subsets
You are given an array nums of integers, all different from each other. Return every subset of
nums.
A subset is any selection of elements from nums, from none of them to all of them, so the empty subset and
the whole array both count. Two subsets are the same when they hold the same values: [1,2] and [2,1] are
one subset. Return each subset exactly once.
The subsets can come back in any order, and so can the values inside each subset. The examples list each subset's values from smallest to largest, and sort the subsets the way a
dictionary sorts words: the empty subset first, and [1] before [1,2].
Example 1
Input: nums = [5, -2, 8]
[[],[-2],[-2,5],[-2,5,8],[-2,8],[5],[5,8],[8]]Explanation: Three elements give eight subsets: the empty one, three that hold one value, three that hold two values, and the whole array.
Example 2
Input: nums = [0]
[[],[0]]Explanation: One element gives two subsets: the empty one and [0]. The empty subset counts even though it holds no
values.
Example 3
Input: nums = [1000000000, -1000000000]
[[],
[-1000000000],
[-1000000000,1000000000],
[1000000000]]Explanation: The values reach −109 and 109. The subset that holds both is shown smallest first,
as [-1000000000,1000000000], but [1000000000,-1000000000] is accepted too.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 16-109 ≤ nums[i] ≤ 109- All the values in
numsare different.
Clarifying questions
What you would ask an interviewer before writing any code.