Recursion and Backtracking Generating every choice
320. Subsets II
You are given an array of integers nums, and the same value can appear in it more than once. Return every
distinct subset of nums.
A subset is what is left after removing any number of elements, from none of them to all of them. So the empty subset and the whole array are both subsets. Two subsets are the same when they hold the same values the same number of times, even if the values come from different positions. Return each distinct subset 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, with the empty subset first.
Example 1
Input: nums = [3, 1, 3]
[[],[1],[1,3],[1,3,3],[3],[3,3]]Explanation: There are 8 ways to choose positions, but the two 3s give the same values: [3] can be either 3, and so can
the 3 in [1,3]. Each of those subsets is listed once, so 6 remain.
Example 2
Input: nums = [-2, 0, -2, -2]
[[],
[-2],
[-2,-2],
[-2,-2,-2],
[-2,-2,-2,0],
[-2,-2,0],
[-2,0],
[0]]Explanation: The 16 ways to choose positions give only 8 distinct subsets. The three −2s are interchangeable, so [-2]
is the same subset whichever −2 it takes, and so is [-2,-2].
Example 3
Input: nums = [1000000000, -1000000000]
[[],
[-1000000000],
[-1000000000,1000000000],
[1000000000]]Explanation: No value repeats, so every way to choose positions gives a different subset, and all 4 appear. The empty subset is one of them.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 14-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.