# Question
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
给出一个包含重复数字的整型数组nums，请你返回所有可能的子集（子集不能重复）
If nums = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
回溯解。得到所有子集只需要每次计算以当前元素为开头的子集即可，但是因为如果输入数组元素重复，按照上面的思路得到的子集会重复，所以我们在遇到相同元素时，对相同元素不能重复计算，即不再计算以该元素为头的子集（因为在第一次遇到的时候已经包含了所有情况），因此我们可以先对输入数组进行排序。
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); backtracking(nums, 0, res, new ArrayList<>()); return res; } /** * 思路：因为输入的数组元素会有重复元素，所以在回溯的过程中相同元素不要重复计算，只计算第一个元素的情况即可。 * 所以我们先对输入数组进行排序，保证重复元素不重复计算 * @param nums：输入数组 * @param start：开始索引 * @param res：保存所有情况 * @param temp：保存当前组合 */ public void backtracking(int[] nums, int start, List<List<Integer>> res, List<Integer> temp){ // 将所有情况添加到结果集 res.add(new ArrayList<>(temp)); // 回溯，计算以i开头的所有组合 for(int i = start;i < nums.length; i++){ // 如果后面的元素和前面的相同，则不计算以当前i开头的组合以防重复计算 if(i > start && nums[i] == nums[i - 1]) continue; temp.add(nums[i]); backtracking(nums, i + 1, res, temp); temp.remove(temp.size() - 1); } }}新闻热点
疑难解答
