Subsets II

Subsets II 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.

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), where n is the length of nums. Each element can be either included or excluded, and sorting is O(n log n), which is dominated by the subset generation. time and O(2^n * n), for storing all possible subsets (each subset can be up to size n, and there are up to 2^n subsets). The recursion stack is O(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

• Backtracking Patterns pattern guide
• Subsets (Include/Exclude) subpattern
• The full DSA patterns sheet
• All coding practice problems

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
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combination Sum — Medium, same pattern
• Combination Sum II — Medium, same pattern