[LeetCode 90] Subsets II

题目链接：subsets-ii

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
        Given a collection of integers that might contain duplicates, S, return all possible subsets.

        Note:
        Elements in a subset must be in non-descending order.
        The solution set must not contain duplicate subsets.
        For example,
        If S = [1,2,2], a solution is:

        [
          [2],
          [1],
          [1,2,2],
          [2,2],
          [1,2],
          []
        ]
 *
 */

public class SubsetsII {

//  19 / 19 test cases passed.
//  Status: Accepted
//  Runtime: 259 ms
//  Submitted: 0 minutes ago

    //时间复杂度O(2^n) 空间复杂度 O(n)
    //偷懒了，直接用了set容器，去除重复子集
    public Set<List<Integer>> subsets = new HashSet<List<Integer>>();
    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        subsets(num, 0, new ArrayList<Integer>());
        return new ArrayList<List<Integer>>(subsets);
    }
    public void subsets(int[] S, int step, List<Integer> subset) {
        if(step == S.length) {
            subsets.add(subset);
            return;
        }
        //num[step] 不加入子集中
        subsets(S, step + 1, new ArrayList<Integer>(subset));

        //num[step] 加入子集中
        subset.add(S[step]);
        subsets(S, step + 1, new ArrayList<Integer>(subset));
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }

}