题目:
题解:
参考LeetCode第78题,这个比较好改,我们只需要判断当前数字和上一个数字是否相同,相同的话跳过即可。当然,要把数字首先进行排序。
画出递归树,在同一层中,第一次add无须考虑是否存在相同的值,但同一层中的后续add操作,如果添加相同的值,那么就是重复运算,这部分是可以去掉的。
解释语句: if cur > begin and candidates[cur-1] == candidates[cur] 是如何避免重复的。
这个避免重复当思想是在是太重要了。
这个方法最重要的作用是,可以让同一层级,不出现相同的元素。即:
例1
1
/ \
2 2 这种情况不会发生 但是却允许了不同层级之间的重复
/ \
5 5
例2
1
/
2 这种情况确是允许的
/
2
为何会有这种神奇的效果呢?
首先 cur-1 == cur 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。
可是问题来了,如果把所有当前与之前一个元素相同的都砍掉,那么例二的情况也会消失。
因为当第二个2出现的时候,他就和前一个2相同了。
那么如何保留例2呢?
那么就用cur > begin 来避免这种情况,你发现例1中的两个2是处在同一个层级上的,
例2的两个2是处在不同层级上的。
在一个for循环中,所有被遍历到的数都是属于一个层级的。我们要让一个层级中,
必须出现且只出现一个2,那么就放过第一个出现重复的2,但不放过后面出现的2。
第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin.
代码:
/** * code90 */
import java.util.*;
public class code90 {
public static List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
dfs(res, list, 0, nums);
return res;
}
public static void dfs(List<List<Integer>> res, List<Integer> list, int start, int nums[]) {
res.add(new ArrayList<>(list));
for (int i = start; i <= nums.length - 1; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
list.add(nums[i]);
dfs(res, list, i + 1, nums);
list.remove(list.size() - 1);
}
}
public static void main(String[] args) {
int nums[] = { 1, 2, 2 };
List<List<Integer>> res = subsetsWithDup(nums);
System.out.println(res);
}
}