Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If nums = , a solution is:
, , , , ,
]
这道题目是Subsets 的变形,数组中包含了重复的元素,之前介绍了两种方法,这里我们可以用同样的方法解决,只要多一个判断结果是否重复就可以了。代码如下: 1,位运算方法
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<Integer> list;
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length == 0)
return result;
java.util.Arrays.sort(nums);
for(int i = 0; i < Math.pow(2, nums.length); i++) {
list = new ArrayList<Integer>();
for(int j = 0; j < nums.length; j++) {
if((i >> j & 1) == 1)
list.add(nums[j]);
}
if(!result.contains(list))
result.add(list);
}
return result;
}
}
2,回溯法
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
LinkedList<Integer> list = new LinkedList<Integer>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length == 0)
return result;
java.util.Arrays.sort(nums);
for(int i = 0; i <= nums.length; i++) {
getSubset(0, i, nums, list, result);
}
return result;
}
public void getSubset(int start, int lth, int[] nums, LinkedList<Integer> list, List<List<Integer>> result) {
if(list.size() == lth) {
if(!result.contains(list))
result.add(new LinkedList<Integer>(list));
return;
}
for(int i = start; i < nums.length; i++) {
list.add(nums[i]);
getSubset(i + 1, lth, nums, list, result);
list.removeLast();
}
}
}
上面的代码都可以通过测试,但是我们还可以将我们的代码优化,在回溯的时候,如果后面的元素和前面的元素相同,我们就可以跳过这个元素,这样就大大提高了效率。代码如下:
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
LinkedList<Integer> list = new LinkedList<Integer>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length == 0)
return result;
java.util.Arrays.sort(nums);
getSubset(0, nums, list, result);
return result;
}
public void getSubset(int index, int[] nums, LinkedList<Integer> list, List<List<Integer>> result) {
if(index <= nums.length) {
result.add(new LinkedList<Integer>(list));
}
for(int i = index; i < nums.length; i++) {
if(i != index && nums[i] == nums[i - 1]) continue;
list.add(nums[i]);
getSubset(i + 1, nums, list, result);
list.removeLast();
}
}
}