My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0)
return result;
Arrays.sort(nums);
ArrayList<Integer> subset = new ArrayList<Integer>();
boolean[] isVisited = new boolean[nums.length];
result.add(subset);
getSubsets(0, nums, false, isVisited, subset, result);
return result;
}
private void getSubsets(int begin, int[] nums, boolean isInserted, boolean[] isVisited,
ArrayList<Integer> subset, ArrayList<List<Integer>> result) {
if (isInserted)
result.add(new ArrayList<Integer>(subset));
else {
for (int i = begin; i < nums.length; i++) {
if (i >= 1 && nums[i] == nums[i - 1] && !isVisited[i - 1])
continue;
isVisited[i] = true;
subset.add(nums[i]);
getSubsets(i, nums, true, isVisited, subset, result);
getSubsets(i + 1, nums, false, isVisited, subset, result);
isVisited[i] = false;
subset.remove(subset.size() - 1);
}
}
}
}
My test result:
这道题目和之前的 permutation I, II 很类似，也是在 Subsets 基础上改的。即避免重复。
而避免重复的关键方法，就是一句判断代码。
if (i >= 1 && nums[i] == nums[i - 1] && !isVisited[i - 1])
continue;
用这个就可以避免掉重复数字带来的重复情况。
差不多就这样了。
总结： Array, backtracing
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0)
return ret;
Arrays.sort(nums);
ArrayList<Integer> group = new ArrayList<Integer>();
helper(0, nums, ret, group);
return ret;
}
/**
* used to put all results into ret depending on recursion(dfs)
* if nums[i] == nums[i - 1], skip this element in order to avoid repeating
*/
private void helper(int begin, int[] nums, ArrayList<List<Integer>> ret, ArrayList<Integer> group) {
if (begin >= nums.length) {
ret.add(new ArrayList<Integer>(group));
return;
}
else {
for (int i = begin; i < nums.length; i++) {
if (i > begin && nums[i] == nums[i - 1]) // avoid repeating when traversing with the beginning of same element
continue;
else {
group.add(nums[i]);
helper(i + 1, nums, ret, group);
group.remove(group.size() - 1);
}
}
ret.add(new ArrayList<Integer>(group));
}
}
}
这次我的代码比之前还是要简洁很多的，我看了之前的函数抬头：
private void getSubsets(int begin, int[] nums, boolean isInserted, boolean[] isVisited, ArrayList<Integer> subset, ArrayList<List<Integer>> result) {
...
}
而我这次的函数抬头：
private void helper(int begin, int[] nums, ArrayList<List<Integer>> ret, ArrayList<Integer> group) {
...
}
没有了布尔变量，这样再加一些注释就很容易看清楚逻辑。
我不知道为什么以前会写的那么复杂。看来我还是有进步的。
最主要的就是防止重复。
我一开始简单的写成了 i >= 0
但应该是， i > begin
因为即使后面等于前面，在部分情况下，仍然是可以放进集合的。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) {
return ret;
}
Arrays.sort(nums);
boolean[] isVisited = new boolean[nums.length];
helper(0, nums, ret, new ArrayList<Integer>(), isVisited);
return ret;
}
private void helper(int begin, int[] nums, List<List<Integer>> ret, List<Integer> group, boolean[] isVisited) {
if (begin > nums.length) {
ret.add(new ArrayList<Integer>(group));
}
else {
for (int i = begin; i < nums.length; i++) {
if (i > 0 && !isVisited[i - 1] && nums[i] == nums[i - 1]) {
continue;
}
else {
group.add(nums[i]);
isVisited[i] = true;
helper(i + 1, nums, ret, group, isVisited);
group.remove(group.size() - 1);
isVisited[i] = false;
}
}
ret.add(new ArrayList<Integer>(group));
}
}
}
提交了几次，自己写了出来。和 Combination思路差不多的。
但是看了下自己以前的代码，有个地方写得更好。
如何区分，访问的当前这个元素以及由他导致的subset，是否已经加入到ret中去了。
现在我是用， boolean[] isVisited
但以前就是加了一个判断条件， i > begin 就可以区分出这种情况。
nums[i] == nums[i - 1]
- 正在dfs中，上一层访问了 nums[i - 1], 那么这一层仍然要把 nums[i] 放入subset中
- 正在dfs中，但nums[i] 是dfs的最开始一层，那么他的情况将完全重复nums[i - 1], 所以直接continue
if (i > begin && nums[i] == nums[i - 1]) => 即可区分这种情况，不用再加 boolean[]
Anyway, Good luck, Richardo! -- 08/06/2016
