LeetCode 90. Subsets II



Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:



The problem is a follow-up question for Subset. Also, it is a typical depth-first search coding problem.

We can have a recursion function to add visited subsets to the final results. Remember to make a deep copy when we need to add the subset to the results.

We can skip visiting subset when we find that the next element value has the same value with the previous element.

Video Tutorial

Java Solution

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return results;
        List<Integer> subset = new ArrayList<>();
        toFindAllSubsets(nums, results, subset, 0);
        return results;
    private void toFindAllSubsets(int[] nums, List<List<Integer>> results, List<Integer> subset, int startIndex) {
        results.add(new ArrayList<>(subset));
        for (int i = startIndex; i < nums.length; i++) {
            if (i != startIndex && nums[i] == nums[i - 1]) {
            toFindAllSubsets(nums, results, subset, i + 1);
            subset.remove(subset.size() - 1);            

Leave a Reply

Your email address will not be published. Required fields are marked *