Subsets II (contains duplicates)

xiaoxiao2021-02-28  4

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], [] ] 代码如下:

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class SubsetsIIContainsDuplicates { public List<ArrayList<Integer>> subsetsII(int[] nums){ List<ArrayList<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list,new ArrayList<>(),nums,0); return list; } private void backtrack(List<ArrayList<Integer>> list, ArrayList<Integer> arrayList, int[] nums, int start) { list.add(new ArrayList<>(arrayList)); for(int i=start; i<nums.length;i++){ if(i>start && nums[i]==nums[i-1]) //防止重复的组合出现 continue; arrayList.add(nums[i]); backtrack(list,arrayList,nums,i+1); arrayList.remove(arrayList.size()-1); } } }