Coding

Subsets II

Asked at

Salesforce

Zepto

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array nums, which can have duplicate entries, provide the power set.

Duplicate subsets cannot exist in the solution set. Return the answer in any sequence.

Input : nums = [1, 2, 2] Output : [ [ ] , [1] , [1, 2] , [1, 2, 2] , [2] , [2, 2] ]

Input : nums = [1, 2] Output : [ [ ], [1] , [2] , [1, 2] ]

Input : nums = [1, 3, 3]

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

cpp

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int>& nums) {
        //your code goes here
    }
};

java

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //your code goes here
    }
}

python

class Solution:
    def subsetsWithDup(self, nums):
        #your code goes here

javascript

class Solution {
    subsetsWithDup(nums) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public List<List<int>> SubsetsWithDup(List<int> nums)
    {
        //your code goes here
    }
}

func subsetsWithDup(nums []int) [][]int {

}

Stuck? Show a way to structure it+

01Sort input values.
02Add the current path at every recursion node.
03Iterate from the current start index.
04Skip an equal value when it is not the first choice at this depth.
05Recurse with i plus one after choosing an element.

Reference answer

Sort nums, then run a DFS where every call represents one unique prefix subset. Immediately append a copy of the current path to the result. From start, try each index i; if i is greater than start and nums[i] equals nums[i minus one], skip it at this depth because choosing the second identical value first creates the same subset. Otherwise append nums[i], recurse with i plus one, and backtrack. The i plus one ensures each occurrence is chosen at most once, while different depths can still select multiple equal values, allowing [2, 2]. Sorting plus the depth-local skip avoids needing a hash set and preserves deterministic order. There can be up to 2 to the power n subsets, and copying them costs O(n times 2 to the power n) in the worst case; auxiliary recursion/path space is O(n) excluding output.

Then expect these follow-ups

How would you generate subsets iteratively by multiplicity?
Tests: follow-up reasoning
What changes if output must be ordered by subset size?
Tests: constraint adaptation

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question