180. Subsets II

Medium · Backtracking

Given an array of integers that may contain duplicates, return all possible subsets (the power set). Each subset must appear only once in the result, even if the input has duplicate elements.

The solution set must not contain duplicate subsets. You may return the subsets in any order.

Examples

Example 1
Input: [1, 2, 2]
Output: [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]
Explanation: The array has a duplicate 2. We generate all unique subsets by sorting first, then using backtracking to skip duplicate elements at the same recursion level.
Example 2
Input: [4, 4, 4, 1, 0]
Output: [[], [0], [1], [4], [0, 1], [0, 4], [1, 4], [0, 1, 4], [4, 4], [0, 4, 4], [1, 4, 4], [0, 1, 4, 4], [4, 4, 4], [0, 4, 4, 4], [1, 4, 4, 4], [0, 1, 4, 4, 4]]
Explanation: Multiple duplicates are handled by sorting and skipping duplicate choices at each recursion level. Results are in lexicographic order.

Constraints