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

Hiring now

Salesforce has 1,420 open roles right now

Also hiring: Zepto

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Business Development Representative Belgium Market (Dutch Speaking)
Ireland - Dublin
Service Cloud Account Executive
France - Paris
Summer Intern 2027 - Content Writer
India - Bangalore

Or practice this question first

Next question