Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
For example,
If S =
[1,2,2]
, a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
public class Solution { public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) { Arrays.sort(num); ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>(); if(num==null) { return ret; } ret.add(new ArrayList<Integer>()); HashSet<String> keys = new HashSet<String>(); for(int i=0;i<num.length;i++) { int s = num[i]; ArrayList<ArrayList<Integer>> add = new ArrayList<ArrayList<Integer>>(); for(ArrayList<Integer> lst : ret) { ArrayList<Integer> lst2 = new ArrayList<Integer>(lst); lst2.add(s); add.add(lst2); } for(ArrayList<Integer> lst : add) { StringBuilder sb = new StringBuilder(); for(Integer in : lst) { sb.append(in.intValue()).append("_"); } if(!keys.contains(sb.toString())) { ret.add(lst); keys.add(sb.toString()); } } } return ret; } }
=========================
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) { return ret; } Arrays.sort(nums); helper(nums, 0, new ArrayList<Integer>(), ret); return ret; } private void helper(int[] nums, int cur, List<Integer> curList, List<List<Integer>> ret) { List<Integer> newList = new ArrayList<Integer>(curList); ret.add(newList); for (int i = cur; i < nums.length; i++) { curList.add(nums[i]); helper(nums, i + 1, curList, ret); curList.remove(curList.size() - 1); while (i != nums.length - 1 && nums[i] == nums[i + 1]) { i++; } } } }
=========
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); helper(nums, 0, new ArrayList<>(), res); return res; } private void helper(int[] nums, int cur, List<Integer> list, List<List<Integer>> res) { List<Integer> newList = new ArrayList<>(list); res.add(newList); for (int i = cur; i < nums.length; i++) { if (i != cur && nums[i] == nums[i - 1]) continue; list.add(nums[i]); helper(nums, i + 1, list, res); list.remove(list.size() - 1); } } }
没有评论:
发表评论