90. Subsets II
Subsets II (LeetCode 90) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Subsets (Include/Exclude) subpattern.
How to solve Subsets II
Subsets II is a Generate Subsets problem, part of Backtracking Patterns. Generate all subsets using include/exclude decision pattern. Handle duplicates in subsets.
Work towards the solution in these steps:
- Consider using backtracking to explore all possible subset combinations by deciding to include or exclude each element.
- Since the input array may contain duplicates, think about sorting it first to bring duplicates together, which can help in avoiding duplicate subsets.
- While iterating through the sorted array, if you encounter a duplicate element, consider skipping the recursive call for that duplicate under certain conditions to prevent generating duplicate subsets.
The reference solution runs in O(2^n) time and O(2^n * n) space.
The Subsets II solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
Topics and companies
Topics: Array, Backtracking, Bit Manipulation.
Reported in interviews at Amazon, ByteDance.
How to practise Subsets II on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(2^n) time and O(2^n * n) space.
Open Subsets II in the code editor, or read the Subsets II editorial for a worked solution with its approach and complexity analysis.
Where Subsets II sits in the DSA pattern sheet
Problems related to Subsets II
Other problems that use the same Subsets (Include/Exclude) and Backtracking Patterns techniques:
- Combinations — Medium, same subpattern
- Letter Combinations of a Phone Number — Medium, same subpattern
- Subsets — Medium, same subpattern
- Sum of All Subset XOR Totals — Easy, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combination Sum — Medium, same pattern
Subsets II FAQ
What is the LeetCode number of Subsets II?
Subsets II is LeetCode problem 90, rated Medium.
What pattern is used to solve Subsets II?
Subsets II is a Generate Subsets problem. It belongs to the Backtracking Patterns pattern, in the Subsets (Include/Exclude) subpattern.
What is the time complexity of Subsets II?
The reference solution runs in O(2^n) time and O(2^n * n) space.
Which companies ask Subsets II?
Subsets II has been reported in interviews at Amazon, ByteDance.