Java: Subsets II

Thought Process

To generate all unique subsets of a given array (which may contain duplicates), we use backtracking. First, we sort the array to group duplicates together. During the backtracking process, we skip duplicate elements to avoid redundant subsets. This ensures that we generate all unique subsets efficiently. 

class Solution {
    
    public void backTrack(List<List<Integer>> ans, List<Integer> tmp, int[] nums,int start){

        ans.add(new ArrayList<>(tmp));

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

            // To remove the duplicates, if current element is equal to previous elememt
            // then we will skip the iteration.
            if(i>start && nums[i]==nums[i-1])
                continue;
            tmp.add(nums[i]);
            backTrack(ans,tmp,nums,i+1);
            tmp.remove(tmp.size()-1);
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(nums);

        backTrack(ans,tmp,nums,0);

        return ans;
    }
}

Code Complexity

Time Complexity: O(2n)

The algorithm generates all possible subsets of the input array, resulting in 2n subsets, where 'n' is the size of the input. Sorting adds an additional O(n log n).

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary list stores intermediate results.

Code copied!