题目主要信息

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

返回的答案中不能包含重复的子集，将答案按字典序进行排序。

方法一：排序+回溯

具体方法

由于题目要求最终答案需要按照字典序排序输出，所以在进行回溯之前先讲数组排序，然后在使用回溯求所有的子集。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        // write code here
        ArrayList<Integer> temp = new ArrayList<>();
        // 排序
        Arrays.sort(nums);
        dfs(nums,temp,0);
        return res;
    }
    public void dfs(int []nums,ArrayList<Integer> temp,int index){
        // 当前加入结果集中
        res.add(new ArrayList<>(temp));
        for(int i=index;i<nums.length;i++){
            // 剪枝
            if(i>index && nums[i] == nums[i-1])
                continue;
            temp.add(nums[i]);
            dfs(nums,temp,i+1);
            temp.remove(temp.size()-1);
        }
    }
}

复杂度分析

• 时间复杂度：$O(n\ast 2^n)O(n*\; 2\; ^n)$。因为每一个元素的状态无外乎取与不取，一共$2^{n}2^n$种状态，每种状态都需要 $O(n)O(n)$ 的构造时间，最终时间复杂度为$O(n\ast 2^n)O(n*\; 2\; ^n)$。
• 空间复杂度：$O(n)O(n)$，递归深度为n，所以系统栈所用空间为$O(n)\mathrm{.}O(n).$