Leetcode: Subsets II

This is based solely on Leetcode number 1. Now let's get started here. 

The original problem is as follows: 

Given an integer array nums, return all possible subsets. The solution set must not contain duplicate subsets. 

Here's en example:

[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Here is C++. 

We use recursion for everything.

In each step we have made a copy of the vector. In this case we either add or ignore a vector.

class Solution {

    public:

        vector<int> num;

        int siz;

        vector<vector<int>> solSet;

        vector<vector<int>> subsets(vector<int> &nums) {

            num = nums; //memory address of nums is assigned to num

            siz = num.size();

            vector<int> temp;

            powerset(0, temp); //subset

            return solSet;

        }

        void powerset(int depth, vector<int> v) {

            if(depth == siz) { //if the array is full.

                solSet.push_back(v); //array is full and return the array. 

                return;   //return if the array is already full             

            }

            vector<int> temp;

            temp = v; 

            v.push_back(num[depth]); //add a new element to the vector v. 

            //push this particular array. 

            powerset(depth + 1, v);  //keep going 

            powerset(depth + 1, temp); //backtrack this again to the old "v" array. 

            return; //return if all the recursive calls are done.

        }

};

Now let's get to problem number 2. This time, we want to return all POSSIBLE subsets, not unique subsets. No duplicates are allowed. However, this time, the integer in the array CAN contain duplicates. 

There's no way to achieve under O(2^n). So we have a bitmasking way to solve this issue. 

The first way to solve this issue is through a method called bitmasking. We can represent each array value as 0 and 1, each indicating whether the region is inside of the array or not. 

class Solution {

    public: 

        vector<vector<int>> subsetsWithDup(vector<int>& nums) {

            int n = nums.size();

            //sort this particular subsets, to help identify duplicates in a hashset. 

            sort(nums.begin(), nums.end()); 

            vector<vector<int>> subsets; //number of subsets to return. 

            int maxNumberOfSubsets = pow(2, n) //2^n  total number of operations

            unordered_set<string> seen; //number of seen sets. 

            //iterate through all of the subsets

            for (int subsetIndex = 0; subsetIndex < maxNumberOfSubsets; subsetIndex++) {

                vector<int> currentSubset; //subset inside of the array of subsets.

                string hashcode = "";

                for(int j = 0; j < n; j++) {

                    //generate the bitmask. for each individual element.

                    int mask = 1 << j;

                    int isSet = mask & subsetIndex;

                    if(isSet != 0) {

                        current_subset.push_back(nums[j]);

                        //generate hashcode to get to the seen area

                        hashcode.append(to_string(nums[j]) + ",");

                    }

                }

                //when there is no existing set that is already labelled/inserted

                if(seen.find(hashcode) == seen.end()) {

                    subsets.push_back(current_subset); //push the current subset

                    seen.insert(hashcode); //insert set to the seen table. 

                }

    

            }

            return subsets;

        }

};

Now it's time to head back to backtracking. The key now is to call everything in a recursive manner.

At each function call, add a new subsets to the list of subsets. For every element, decide wheter to keep the element or not. Only this time we will use a hashmap to see if something is a replica or not. Here's the code. 

class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums); //sort the arrays in order.

        List<List<Integer>> subsets = new ArrayList<>(); //subset to return

        List<Integer> currentSubset = new ArrayList<>(); //add - subtract to current subset

        subsetsWithDupHelper(subsets, currentSubset, nums, 0); //modify subsets

        return subsets; //return subsets

    }

    private void subsetsWithDupHelper(List<List<Integer>> subsets, List<Integer> currentSubset, int[] nums, int index) {

        // Add the subset formed so far to the subsets list.

        subsets.add(new ArrayList<>(currentSubset));

        //for every element in side of the array from the index

        for (int i = index; i < nums.length; i++) {

            // If the current element is a duplicate, ignore.

            if (i != index && nums[i] == nums[i - 1]) {

                continue;

            }

            //else add to current subset

            currentSubset.add(nums[i]);

            //carry out recursion

            subsetsWithDupHelper(subsets, currentSubset, nums, i + 1);

            //remove current subset

            currentSubset.remove(currentSubset.size() - 1);

        }

    }

}