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 很類(lèi)似饺汹，也是在 Subsets 基礎(chǔ)上改的。即避免重復(fù)。
而避免重復(fù)的關(guān)鍵方法，就是一句判斷代碼余蟹。
if (i >= 1 && nums[i] == nums[i - 1] && !isVisited[i - 1])
continue;
用這個(gè)就可以避免掉重復(fù)數(shù)字帶來(lái)的重復(fù)情況。
差不多就這樣了子刮。
總結(jié)： 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));
}
}
}
這次我的代碼比之前還是要簡(jiǎn)潔很多的威酒，我看了之前的函數(shù)抬頭：
private void getSubsets(int begin, int[] nums, boolean isInserted, boolean[] isVisited, ArrayList<Integer> subset, ArrayList<List<Integer>> result) {
...
}
而我這次的函數(shù)抬頭：
private void helper(int begin, int[] nums, ArrayList<List<Integer>> ret, ArrayList<Integer> group) {
...
}
沒(méi)有了布爾變量，這樣再加一些注釋就很容易看清楚邏輯挺峡。
我不知道為什么以前會(huì)寫(xiě)的那么復(fù)雜葵孤。看來(lái)我還是有進(jìn)步的橱赠。
最主要的就是防止重復(fù)尤仍。
我一開(kāi)始簡(jiǎn)單的寫(xiě)成了 i >= 0
但應(yīng)該是， i > begin
因?yàn)榧词购竺娴扔谇懊嫦烈蹋诓糠智闆r下吓著，仍然是可以放進(jìn)集合的鲤嫡。
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));
}
}
}
提交了幾次，自己寫(xiě)了出來(lái)绑莺。和 Combination思路差不多的。
但是看了下自己以前的代碼惕耕，有個(gè)地方寫(xiě)得更好纺裁。
如何區(qū)分，訪問(wèn)的當(dāng)前這個(gè)元素以及由他導(dǎo)致的subset司澎，是否已經(jīng)加入到ret中去了欺缘。
現(xiàn)在我是用， boolean[] isVisited
但以前就是加了一個(gè)判斷條件挤安， i > begin 就可以區(qū)分出這種情況谚殊。
nums[i] == nums[i - 1]
- 正在dfs中，上一層訪問(wèn)了 nums[i - 1], 那么這一層仍然要把 nums[i] 放入subset中
- 正在dfs中蛤铜，但nums[i] 是dfs的最開(kāi)始一層嫩絮，那么他的情況將完全重復(fù)nums[i - 1], 所以直接continue
if (i > begin && nums[i] == nums[i - 1]) => 即可區(qū)分這種情況，不用再加 boolean[]
Anyway, Good luck, Richardo! -- 08/06/2016
