第90题：子集II

一． 问题描述

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

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]

输出:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

二． 解题思路

本题思路：采用回溯算法进行求解，构建递归函数（全局变量列表data存储子集，局部变量list存储当前某一个具体子集，n表示添加的位数，nums全局数组）

步骤一：将数组nums从小到大进行排序。

步骤二：构建递归函数，判断list对象是否已经存在于data中，如果不存在则添加，则否跳过。

步骤三：根据n的位置继续添加未加入到list的数字，并且返回步骤二进行递归。

步骤四：得到data列表，返回data。

三． 执行结果

执行用时 :17 ms, 在所有 java 提交中击败了9.14%的用户

内存消耗 :36.6 MB, 在所有 java 提交中击败了94.59%的用户

四． Java代码

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
       Arrays.sort(nums);
        List<List<Integer>> data=new ArrayList<List<Integer>>();
        List<Integer> list=new ArrayList<Integer>();
        sw(data,list,0,nums);
           return data;
    }


    public void sw(List<List<Integer>> data,List<Integer> list,int n,int[] nums)
    {
        if(!data.contains(list))
        {
            data.add(list);
        }
        for(int i=n;i<nums.length;i++)
        {
            List<Integer> alist=new ArrayList<Integer>(list);

            alist.add(nums[i]);
            sw(data,alist,i+1,nums);
        }
    }
}