Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); // 必须排序 List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(nums, 0, path, result); return result; } private static void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> result) { result.add(new ArrayList<Integer>(path)); for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i-1]) continue; path.add(nums[i]); dfs(nums, i + 1, path, result); path.remove(path.size() - 1); } } }
和subsets基本一样,在当前数字等于前一个数字的时候出现重复,需要跳过。
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { //回溯法 List<List<Integer>> result = new ArrayList<List<Integer>>(); Arrays.sort(nums); List<Integer> tmp = new ArrayList<Integer>(); backtrack(result, tmp, nums, 0); return result; } private void backtrack(List<List<Integer>> result, List<Integer> tmp, int[] nums, int start){ //add前需要进行判断result中是否已经包含该元素。有可能重复。 if (!result.contains(tmp)){ result.add(new ArrayList(tmp)); } for (int i = start; i < nums.length; i++){ tmp.add(nums[i]); backtrack(result, tmp, nums, i + 1); tmp.remove(tmp.size() - 1); } } }
但是这样每次判断一下不是更容易理解吗。。。