90. 子集 II

偏执的太偏执、 2024-03-30 12:09 73阅读 0赞

### 90. 子集 II ###

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 **不能** 包含重复的子集。返回的解集中，子集可以按 **任意顺序** 排列。

##### 示例 1： #####

> 输入：nums = \[1,2,2\]  
> 输出：\[\[\],\[1\],\[1,2\],\[1,2,2\],\[2\],\[2,2\]\]

##### 示例 2： #####

> 输入：nums = \[0\]  
> 输出：\[\[\],\[0\]\]

##### 提示： #####

1 <= nums.length <= 10  
\-10 <= nums\[i\] <= 10

#### 思路：(回溯) ####

*  回溯常规思路，类似回溯题目：[40. 组合总和 II][40. _ II]
 *  回溯万能模板：[46. 全排列][46.]
 *  本题关键：重复元素的处理，重要思想为设置访问次序：

if(i > 0 && hasVisited[i - 1] == false && nums[i] == nums[i - 1]) {
    	continue;
    }

详细解释见：[47. 全排列 II][47. _ II]

#### 代码：(Java) ####

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class subSetsTwo {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int [] nums = {
        1, 2, 2};
    		System.out.println(subsetsWithDup(nums));
    	}
    	public static List<List<Integer>> subsetsWithDup(int[] nums) {
        
    		List<List<Integer>> combinations = new ArrayList<>();
    		List<Integer> combination = new ArrayList<>();
    		combinations.add(new ArrayList<>(combination));
    		Arrays.sort(nums);
    		boolean [] hasVisited = new boolean[nums.length];
    		for(int k = 1; k <= nums.length ; k++) {
        
    			backtracking(combinations, combination, hasVisited, nums, 0, k);
    		}
    		return combinations;
        }
    	private static void backtracking(List<List<Integer>> combinations, List<Integer> combination, boolean[] hasVisited, int[] nums, int start, int k) {
        
    		// TODO Auto-generated method stub
    		if(k == 0) {
        
    			combinations.add(new ArrayList<> (combination));
    			return;
    		}
    		if(nums.length - start < k) {
        
    			return;
    		}
    		for(int i = start; i < nums.length; i++) {
        
    			if(i > 0 && hasVisited[i - 1] == false && nums[i] == nums[i - 1]) {
        
    				continue;
    			}
    			combination.add(nums[i]);
    			hasVisited[i] = true;
    			backtracking(combinations, combination, hasVisited, nums, i + 1, k - 1);
    			hasVisited[i] = false;
    			combination.remove(combination.size() - 1);
    		}
    	}
    }

##### 运行结果： #####

![在这里插入图片描述][4a293565d5da4598a64969ba3907711e.png]

##### 注：仅供学习参考！ #####

题目来源：[力扣.][.]

[40. _ II]: https://blog.csdn.net/weixin_43412762/article/details/128430757?spm=1001.2014.3001.5501
[46.]: https://blog.csdn.net/weixin_43412762/article/details/128160319?spm=1001.2014.3001.5501
[47. _ II]: https://blog.csdn.net/weixin_43412762/article/details/128172523
[4a293565d5da4598a64969ba3907711e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0c306c2174dc487ca740c36afa11d3cf.png
[.]: https://leetcode.cn/problems/subsets-ii/description/