LeetCode - Subsets II

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.

Problem statement taken from: https://leetcode.com/problems/subsets-ii.

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

Explanation

Backtracking

The approach for this problem is similar to our previous blog LeetCode Subsets. The only difference is we need to exclude duplicate elements here while generating the subset.

First, we will sort the nums array. We can either exclude the duplicate elements while recursively calling the subset generator function or we can mark the subset as a Set (Set is an abstract data type that can store unique values).

Let's check the algorithm first.

// subsetsWithDup(nums) function
- sort nums array sort(nums.begin(),nums.end())

- initialize vector<int> subset
             set<vector<int>> result
             vector<vector<int>> answer

- call util function subsetsUtil(nums, result, subset, 0)

- push set result in vector array
  loop for(auto it:result)
         answer.push_back(it)

- return answer

// subsetsUtil(nums, result, subset, index) function
- insert subset in result
  result.insert(subset)

- loop for i = index; i < nums.size(); i++
  - subset.push_back(nums[i])

  - subsetsUtil(nums, result, subset, i + 1)

  - subset.pop_back()

Let's check out our solutions in C++, Golang, and Javascript. Note: In the C++ solution the subset is a Set, while in Golang and Javascript it's a normal array and we have ignored the duplicates.

C++ solution

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int> subset;
        set<vector<int>> result;

        subsetsUtil(nums, result, subset, 0);

        vector<vector<int>> answer;

        for(auto it:result){
            answer.push_back(it);
        }

        return answer;
    }

public:
    void subsetsUtil(vector<int>& nums, set<vector<int>>& result, vector<int>& subset, int index) {
        result.insert(subset);

        for(int i = index; i < nums.size(); i++){
            subset.push_back(nums[i]);

            subsetsUtil(nums, result, subset, i + 1);

            subset.pop_back();
        }

        return;
    }
};

Golang solution

func subsetsUtils(nums, subset []int, result *[][]int) {
    cp := make([]int, len(subset))
    copy(cp, subset)

    *result = append(*result, cp)

    for i := 0; i < len(nums); i++ {
        subsetsUtils(nums[i+1:], append(subset, nums[i]), result)

        for ; i < len(nums)-1 && nums[i] == nums[i+1]; i++ {
        }
    }
}

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)

    var result [][]int
    subset := make([]int, 0, len(nums))

    subsetsUtils(nums, subset, &result)

    return result
}

Javascript solution

var subsetsWithDup = function(nums) {
    nums.sort((a, b) => a - b);

    const result = [];

    subsetsUtils(0, []);

    return result;

    function subsetsUtils (index, array) {
        result.push([...array]);

        for (let i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }

            array.push(nums[i]);
            subsetsUtils(i + 1, array);
            array.pop();
        }
    }
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: nums = [1, 2, 2]

Step 1: sort(nums.begin(),nums.end())
        nums = [1, 2, 3]

Step 2: initialize vector<int> subset
                   set<vector<int>> result

Step 3: subsetsUtil(nums, result, subset, 0)

// in subsetsUtils function
Step 4: result.push_back(subset)
        result.push_back([])

        result = [[]]

        loop for i = index, i < nums.size()
        i = 0
        0 < 3
        true

        subset.push_back(nums[i])
        subset.push_back(nums[0])
        subset.push_back(1)

        subset = [1]

        subsetsUtil(nums, res, subset, i + 1)
        subsetsUtil([1, 2, 2], [[]], [1], 0 + 1)
        subsetsUtil([1, 2, 2], [[]], [1], 1)

Step 5: result.push_back(subset)
        result.push_back([1])

        result = [[], [1]]

        loop for i = index, i < nums.size()
        i = 1
        1 < 3
        true

        subset.push_back(nums[i])
        subset.push_back(nums[1])
        subset.push_back(2)

        subset = [1, 2]

        subsetsUtil(nums, res, subset, i + 1)
        subsetsUtil([1, 2, 2], [[], [1]], [1, 2], 1 + 1)
        subsetsUtil([1, 2, 2], [[], [1]], [1, 2], 2)

Step 6: result.push_back(subset)
        result.push_back([1, 2])

        result = [[], [1], [1, 2]]

        loop for i = index, i < nums.size()
        i = 2
        2 < 3
        true

        subset.push_back(nums[i])
        subset.push_back(nums[2])
        subset.push_back(2)

        subset = [1, 2, 2]

        subsetsUtil(nums, res, subset, i + 1)
        subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2, 2], 2 + 1)
        subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2, 2], 3)

Step 7: result.push_back(subset)
        result.push_back([1, 2, 3])

        result = [[], [1], [1, 2], [1, 2, 3]]

        loop for i = index, i < nums.size()
        i = 3
        3 < 3
        false

Step 8: Here we backtrack to last line of Step 6 where
        i = 2
        subset = [1, 2, 2]

        We execute the next line
        subset.pop()

        subset = [1, 2]

Step 9: We backtrack to last line of Step 5 where
        i = 1
        subset = [1, 2]

        We execute the next line
        subset.pop()

        subset = [1]

Step 10: For loop continues where we execute
        loop for i = index, i < nums.size()
        i = 2
        i < nums.size()
        2 < 3
        true

        subset.push_back(nums[i])
        subset.push_back(nums[2])
        subset.push_back(2)

        subset = [1, 2]

        subsetsUtil(nums, res, subset, i + 1)
        subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2], 2 + 1)
        subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [1, 2], 3)

Step 11: result.push_back(subset)
         result.push_back([1, 2])

         result = [[], [1], [1, 2], [1, 2, 2]]

         loop for i = index, i < nums.size()
         i = 3
         3 < 3
         false

Step 12: Here we backtrack to last line of Step 3 where
         i = 0
         subset = [1]

         We execute the next line
         subset.pop()

         subset = []

Step 13: For loop continues where we execute
         loop for i = index, i < nums.size()
         i = 1
         i < nums.size()
         1 < 3
         true

         subset.push_back(nums[i])
         subset.push_back(nums[1])
         subset.push_back(2)

         subset = [2]

         subsetsUtil(nums, res, subset, i + 1)
         subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [2], 1 + 1)
         subsetsUtil([1, 2, 2], [[], [1], [1, 2]], [2], 2)

Step 14: result.push_back(subset)
         result.push_back([2])

         result = [[], [1], [1, 2], [1, 2, 2], [1, 2], [2]]

         loop for i = index, i < nums.size()
         i = 2
         2 < 3
         true

         subset.push_back(nums[i])
         subset.push_back(nums[2])
         subset.push_back(2)

         subset = [2, 2]

         subsetsUtil(nums, res, subset, i + 1)
         subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2]], [2, 2], 2 + 1)
         subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2]], [2, 2], 3)

Step 15: result.push_back(subset)
         result.push_back([2, 2])

         result = [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

         loop for i = index, i < nums.size()
         i = 3
         3 < 3
         false

Step 16: Here we backtrack to last line of Step 14 where
         i = 2
         subset = [2, 2]

         We execute the next line
         subset.pop()

         subset = [2]

Step 17: Here we backtrack to last line of Step 13 where
         i = 1
         subset = [2]

         We execute the next line
         subset.pop()

         subset = []

Step 18: For loop continues where we execute
         loop for i = index, i < nums.size()
         i = 2
         i < nums.size()
         2 < 3
         true

         subset.push_back(nums[i])
         subset.push_back(nums[2])
         subset.push_back(2)

         subset = [2]

         subsetsUtil(nums, res, subset, i + 1)
         subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2], [2, 2]], [2], 2 + 1)
         subsetsUtil([1, 2, 2], [[], [1], [1, 2], [2], [2, 2]], [2], 3)

Step 19: result.push_back(subset)
         result.push_back([2])

         result = [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

         loop for i = index, i < nums.size()
         i = 3
         3 < 3
         false

Step 20: We have no more stack entries left. We return to the main function.

Step 21: for(auto it:result){
            answer.push_back(it);
        }

        We push result Set to answer Vector.

Step 22: return answer

So we return the answer as [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]].