【LeetCode】90. 子集 II（Java）

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

解法一

迭代

class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { //迭代 //因为集合中如果元素相同，但位置不同，也算重复，所以需要先进行排序 Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); res.add(new ArrayList<>()); for (int num : nums) { int size = res.size(); for (int i = 0; i < size; i++) { List<Integer> temp = new ArrayList<>(res.get(i)); temp.add(num); //比第78题子集多了个判断，其余的都一样 if (!res.contains(temp)) res.add(temp); } } return res; } }

解法二

回溯

class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { //回溯 //排序，避免重复 Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); backtrack(nums, 0, res, new ArrayList<>()); return res; } private void backtrack(int[] nums, int start, List<List<Integer>> res, List<Integer> cur) { res.add(new ArrayList<>(cur)); for (int i = start; i < nums.length; i++) { //当前值不是循环的首位，并且当前值等于前一个值，跳过，避免重复 if (i > start && nums[i] == nums[i - 1]) continue; cur.add(nums[i]); backtrack(nums, i + 1, res, cur); cur.remove(cur.size() - 1); } } }