78. Subsets
Subsets (LeetCode 78) 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
Subsets 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 as a systematic way to explore all possible combinations in the input array.
- Think about how to represent a subset at each step and how to decide whether to include or exclude the current element.
- At each recursive call, you have two choices for the current element: either include it in the subset or skip it; explore both paths.
The reference solution runs in O(n * 2^n) time and O(n * 2^n) space.
The Subsets solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer array nums of unique elements, 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,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- All the numbers of nums are unique.
Topics and companies
Topics: Array, Backtracking, Bit Manipulation.
Reported in interviews at Facebook, Bloomberg, Amazon, Uber, Microsoft, Apple, ByteDance.
How to practise Subsets 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(n * 2^n) time and O(n * 2^n) space.
Open Subsets in the code editor, or read the Subsets editorial for a worked solution with its approach and complexity analysis.
Where Subsets sits in the DSA pattern sheet
Problems related to Subsets
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 II — 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 FAQ
What is the LeetCode number of Subsets?
Subsets is LeetCode problem 78, rated Medium.
What pattern is used to solve Subsets?
Subsets 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?
The reference solution runs in O(n * 2^n) time and O(n * 2^n) space.
Which companies ask Subsets?
Subsets has been reported in interviews at Facebook, Bloomberg, Amazon, Uber, Microsoft, Apple, ByteDance.