Java solution || recursion || beats 100%
Here, I have used a recursive approach where we pick the first occurrence of every unique element in every recursive call.\n\nApproach:\nBrute force: Follow a g
Here, I have used a recursive approach where we pick the first occurrence of every unique element in every recursive call.\n\nApproach:\nBrute force: Follow a general subsequence pattern using recursion and add every subsequence to the final ArrayList. Then convert the ArrayList to a HashSet and again convert it back to an ArrayList. This process takes extra time while converting the ArrayList to a HashSet and then back to an ArrayList.\n\nWe can avoid these extra conversions while doing the subsequence recursion.\n\nOptimized approach: Initially, sort the array because we need all duplicate elements consecutively. Start the recursion and add the list to the "ans" (final ArrayList). Run a for loop because we need to go through every possibility of a subsequence from the current element to the end of the array.\n\nIf (i != ind && arr[i] == arr[i-1]), continue;\n\nThis condition is used to check if the current element is a duplicate or the first occurrence. If it is a duplicate, we continue the loop without adding it to the list. Otherwise, we add it to the list and make further recursive calls for other elements. Make sure to remove the last element of the list while backtracking to reconstruct the previous list.\n\nTime complexity: O(2^n * n)\n- 2^n is the worst case of the number of subsequences formed. This occurs when all elements are unique.\n- n is for adding the list to "ans.\n\nSpace complexity : O(2^n * k)\n\n- 2^n is number of sub ArrayLists(list) in the final ArrayLists(ans)\n- k is average size of sub ArrayList(list) \n\n```\nclass Solution {\n    public List<List<Integer>> subsetsWithDup(int[] nums) {\n        Arrays.sort(nums);\n        List<List<Integer>> ans = new ArrayList<>();\n        ArrayList<Integer> list=new ArrayList<>();\n        subset2(0,nums,list,ans);\n        return ans;\n    }\n\n    private void subset2(int ind, int[] arr, ArrayList<Integer> list, List<List<Integer>> ans) {\n        ans.add(new ArrayList<>(list));\n        for(int i=ind;i<arr.length;i++){\n            if(i!=ind && arr[i]==arr[i-1]) continue;\n            list.add(arr[i]);\n            subset2(i+1,arr,list,ans);\n            list.remove(list.size()-1);\n        }\n    }\n}\n```
['Recursion', 'Java']