[LeetCode] 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

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

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

Thought process:
Based on the solution to "78. Subsets", sort the array before recursion. For each iteration, if current index is larger than the starting index of this recurrence, and current number equals its previous number, that means it'll create a duplicate subset if it's added to the current subset, because that subset has already been accounted for by the previous number. So continue.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> subsets = new ArrayList<>(); List<Integer> subset = new ArrayList<>(); Arrays.sort(nums); subsetsWithDup(nums, 0, subset, subsets); return subsets; } private void subsetsWithDup(int[] nums, int start, List<Integer> subset, List<List<Integer>> subsets) { subsets.add(new ArrayList<>(subset)); for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i - 1]) { continue; } subset.add(nums[i]); subsetsWithDup(nums, i + 1, subset, subsets); subset.remove(subset.size() - 1); } } }

Time complexity:
Sorting takes O(nlogn). Finding subsets takes O(2^n). The overall time complexity is O(2^n).