Subsets II

Medium · Backtracking

You are given an array of integers that may contain duplicate values. Return all possible subsets of the array, including the empty subset and the full array, but without producing the same subset combination twice even when repeated values could otherwise create identical results. The order of the subsets in the output and the order of elements returned within each subset do not matter, only which distinct groups of values appear.

Examples

Input:  nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Why:    Since two 2s are identical, subsets that would repeat like picking the first 2 alone versus the second 2 alone are only counted once.

Input:  nums = [0]
Output: [[],[0]]
Why:    A single element gives only the empty set and the set with that element.

Input:  nums = [4,4,4]
Output: [[],[4],[4,4],[4,4,4]]
Why:    All three values are the same, so the distinct subsets are just determined by how many copies of 4 are included.

Constraints

1 <= nums.length <= 10, -10 <= nums[i] <= 10

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Subsets II

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Subsets II. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.