题目描述（中等难度）

78题升级版，大家可以先做 78 题。给定一个数组，输出所有它的子数组。区别在于，这道题给定的数组中，出现了重复的数字。 直接根据 78 题的思路去做。

解法一 回溯法

这个比较好改，我们只需要判断当前数字和上一个数字是否相同，相同的话跳过即可。当然，要把数字首先进行排序。 1. public List> subsetsWithDup(int[] nums) { 2. List> ans = new ArrayList<>(); 3. Arrays.sort(nums); //排序 4. getAns(nums, 0, new ArrayList<>(), ans); 5. return ans; 6. } 7. 8. private void getAns(int[] nums, int start, ArrayList temp, List> ans) { 9. ans.add(new ArrayList<>(temp)); 10. for (int i = start; i < nums.length; i++) { 11. //和上个数字相等就跳过 12. if (i > start && nums[i] == nums[i - 1]) { 13. continue; 14. } 15. temp.add(nums[i]); 16. getAns(nums, i + 1, temp, ans); 17. temp.remove(temp.size() - 1); 18. } 19. }

时间复杂度： 空间复杂度：

解法二 迭代法

根据78题解法二修改。我们看一下如果直接按照 78 题的思路会出什么问题。之前的思路是，先考虑 0 个数字的所有子串，再考虑 1 个的所有子串，再考虑 2 个的所有子串。而求 n 个的所有子串，就是 【n - 1 的所有子串】和 【n - 1 的所有子串加上 n】。例如， 1. 数组 [ 1 2 3 ] 2. [ ]的所有子串 [ ] 3. [ 1 ] 个的所有子串 [ ] [ 1 ] 4. [ 1 2 ] 个的所有子串 [ ] [ 1 ] [ 2 ][ 1 2 ] 5. [ 1 2 3 ] 个的所有子串 [ ] [ 1 ] [ 2 ] [ 1 2 ] [ 3 ] [ 1 3 ] [ 2 3 ] [ 1 2 3 ]

但是如果有重复的数字，会出现什么问题呢 1. 数组 [ 1 2 2 ] 2. [ ] 的所有子串 [ ] 3. [ 1 ] 的所有子串 [ ] [ 1 ] 4. [ 1 2 ] 的所有子串 [ ] [ 1 ] [ 2 ][ 1 2 ] 5. [ 1 2 2 ] 的所有子串 [ ] [ 1 ] [ 2 ] [ 1 2 ] [ 2 ] [ 1 2 ] [ 2 2 ] [ 1 2 2 ]

我们发现出现了重复的数组，那么我们可不可以像解法一那样，遇到重复的就跳过这个数字呢？答案是否定的，如果最后一步 [ 1 2 2 ] 增加了 2 ，跳过后，最终答案会缺少 [ 2 2 ]、[ 1 2 2 ] 这两个解。我们仔细观察这两个解是怎么产生的。 我们看到第 4 行黑色的部分，重复了，是怎么造成的呢？ 第 4 行新添加的 2 要加到第 3 行的所有解中，而第 3 行的一部分解是旧解，一部分是新解。可以看到，我们黑色部分是由第 3 行的旧解产生的，橙色部分是由新解产生的。 而第 1 行到第 2 行，已经在旧解中加入了 2 产生了第 2 行的橙色部分，所以这里如果再在旧解中加 2 产生黑色部分就造成了重复。 所以当有重复数字的时候，我们只考虑上一步的新解，算法中用一个指针保存每一步的新解开始的位置即可。 1. public List> subsetsWithDup(int[] nums) { 2. List> ans = new ArrayList<>(); 3. ans.add(new ArrayList<>());// 初始化空数组 4. Arrays.sort(nums); 5. int start = 1; //保存新解的开始位置 6. for (int i = 0; i < nums.length; i++) { 7. List> ans_tmp = new ArrayList<>(); 8. // 遍历之前的所有结果 9. for (int j = 0; j < ans.size(); j++) { 10. List list = ans.get(j); 11. //如果出现重复数字，就跳过所有旧解 12. if (i > 0 && nums[i] == nums[i - 1] && j < start) { 13. continue; 14. } 15. List tmp = new ArrayList<>(list); 16. tmp.add(nums[i]); // 加入新增数字 17. ans_tmp.add(tmp); 18. } 19. 20. start = ans.size(); //更新新解的开始位置 21. ans.addAll(ans_tmp); 22. } 23. return ans; 24. }

时间复杂度： 空间复杂度：O（1）。 还有一种思路，参考这里，当有重复数字出现的时候我们不再按照之前的思路走，而是单独考虑这种情况。 当有 n 个重复数字出现，其实就是在出现重复数字之前的所有解中，分别加 1 个重复数字， 2 个重复数字，3 个重复数字 … 什么意思呢，看一个例子。 1. 数组 [ 1 2 2 2 ] 2. [ ]的所有子串 [ ] 3. [ 1 ] 个的所有子串 [ ] [ 1 ] 4. 然后出现了重复数字 2，那么我们记录重复的次数。然后遍历之前每个解即可 5. 对于 [ ] 这个解， 6. 加 1 个 2，变成 [ 2 ] 7. 加 2 个 2，变成 [ 2 2 ] 8. 加 3 个 2，变成 [ 2 2 2 ] 9. 对于 [ 1 ] 这个解 10. 加 1 个 2，变成 [ 1 2 ] 11. 加 2 个 2，变成 [ 1 2 2 ] 12. 加 3 个 2，变成 [ 1 2 2 2 ]

代码的话，就很好写了。 1. public List> subsetsWithDup(int[] num) { 2. List> result = new ArrayList>(); 3. List empty = new ArrayList(); 4. result.add(empty); 5. Arrays.sort(num); 6. 7. for (int i = 0; i < num.length; i++) { 8. int dupCount = 0; 9. //判断当前是否是重复数字，并且记录重复的次数 10. while( ((i+1) < num.length) && num[i+1] == num[i]) { 11. dupCount++; 12. i++; 13. } 14. int prevNum = result.size(); 15. //遍历之前几个结果的每个解 16. for (int j = 0; j < prevNum; j++) { 17. List element = new ArrayList(result.get(j)); 18. //每次在上次的结果中多加 1 个重复数字 19. for (int t = 0; t <= dupCount; t++) { 20. element.add(num[i]); //加入当前重复的数字 21. result.add(new ArrayList(element)); 22. } 23. } 24. } 25. return result; 26. }

解法三 位操作

本以为这个思路想不出来怎么去改了，然后看到了这里。 回顾一下，这个题的思想就是每一个数字，考虑它的二进制表示。 例如，nums = [ 1, 2 , 3 ]。用 1 代表在，0 代表不在。 1. 1 2 3 2. 0 0 0 -> [ ] 3. 0 0 1 -> [ 3] 4. 0 1 0 -> [ 2 ]
5. 0 1 1 -> [ 2 3]
6. 1 0 0 -> [1 ] 7. 1 0 1 -> [1 3] 8. 1 1 0 -> [1 2 ] 9. 1 1 1 -> [1 2 3]

但是如果有了重复数字，很明显就行不通了。例如对于 nums = [ 1 2 2 2 3 ]。 1. 1 2 2 2 3 2. 0 1 1 0 0 -> [ 2 2 ] 3. 0 1 0 1 0 -> [ 2 2 ] 4. 0 0 1 1 0 -> [ 2 2 ]

上边三个数产生的数组重复的了。三个中我们只取其中 1 个，取哪个呢？取从重复数字的开头连续的数字。什么意思呢？就是下边的情况是我们所保留的。 1. 2 2 2 2 2 2. 1 0 0 0 0 -> [ 2 ] 3. 1 1 0 0 0 -> [ 2 2 ] 4. 1 1 1 0 0 -> [ 2 2 2 ] 5. 1 1 1 1 0 -> [ 2 2 2 2 ] 6. 1 1 1 1 1 -> [ 2 2 2 2 2 ]

而对于 [ 2 2 ] 来说，除了 1 1 0 0 0 可以产生，下边的几种情况，都是产生的 [ 2 2 ] 1. 2 2 2 2 2 2. 1 1 0 0 0 -> [ 2 2 ] 3. 1 0 1 0 0 -> [ 2 2 ] 4. 0 1 1 0 0 -> [ 2 2 ] 5. 0 1 0 1 0 -> [ 2 2 ] 6. 0 0 0 1 1 -> [ 2 2 ] 7. ......

怎么把 1 1 0 0 0 和上边的那么多种情况区分开来呢？我们来看一下出现了重复数字，并且当前是 1 的前一个的二进位。 对于 1 1 0 0 0 ，是 1。 对于 1 0 1 0 0 , 是 0。 对于 0 1 1 0 0 ，是 0。 对于 0 1 0 1 0 ，是 0。 对于 0 0 0 1 1 ，是 0。 …… 可以看到只有第一种情况对应的是 1 ，其他情况都是 0。其实除去从开头是连续的 1 的话，就是两种情况。 第一种就是，占据了开头，类似于这种 10 …1…. 第二种就是，没有占据开头，类似于这种 0 …1… 这两种情况，除了第一位，其他位的 1 的前边一定是 0。所以的话，我们的条件是看出现了重复数字，并且当前位是 1 的前一个的二进位。 所以可以改代码了。 1. public List> subsetsWithDup(int[] num) { 2. Arrays.sort(num); 3. List> lists = new ArrayList<>(); 4. int subsetNum = 1<<num.length; 5. for(int i=0;i<subsetNum;i++){ 6. List list = new ArrayList<>(); 7. boolean illegal=false; 8. for(int j=0;j>j&1)==1){ 11. //当前是重复数字，并且前一位是 0，跳过这种情况 12. if(j>0&&num[j]==num[j-1]&&(i>>(j-1)&1)==0){ 13. illegal=true; 14. break; 15. }else{ 16. list.add(num[j]); 17. } 18. } 19. } 20. if(!illegal){ 21. lists.add(list); 22. } 23. 24. } 25. return lists; 26. }

总

解法一和解法二怎么改，分析一下比较容易想到。解法三就比较难了，突破口就是选一个特殊的结构做代表，和其他情况区分出来。而从头开始的连续 1 可能就会是我们第一个想到的数，然后分析一下，发现果然可以和其他所有情况区分开来。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情