leetcode90. Subsets II

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], [] ]

解法

回溯法

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