public class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();

        res.add(new ArrayList<>()); 

        for (int num: nums) {

            List<List<Integer>> resDup = new ArrayList<>(res);

            for (List<Integer> list:resDup) {

                List<Integer> tmpList = new ArrayList<>(list);

                list.add(num);

                res.add(tmpList);

            }

        }

        return res;

    }

}

https://leetcode.com/problems/subsets-ii/

// 好像跟之前也用的类似的方法

package com.company;

import java.util.*;

class Solution {

    class Pos {

        int pos;

        int len;

        Pos(int pos, int len) {

            this.pos = pos;

            this.len = len;

        }

    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);

        Queue<List<Integer>> qe = new ArrayDeque();

        Map<Integer, Pos> mp = new HashMap();

        List<List<Integer>> ret = new ArrayList<>();

        int len = 0;

        for (int i=0; i<nums.length; i++) {

            if (i == 0 || nums[i] == nums[i-1]) {

                len++;

            }

            else {

                Pos pos = new Pos(i-len, len);

                mp.put(nums[i-1], pos);

                len = 1;

            }

        }

        Pos pos = new Pos(nums.length-len, len);

        mp.put(nums[nums.length-1], pos);

        List<Integer> lst = new ArrayList();

        qe.offer(lst);

        ret.add(lst);

        while (!qe.isEmpty()) {

            List<Integer> tmpLst = qe.poll();

            boolean empty = true;

            int lastInt = 0;

            int curSize = -1;

            int curTail = nums[0];

            if (!tmpLst.isEmpty()) {

                empty = false;

                lastInt = tmpLst.get(tmpLst.size() - 1);

                curSize = tmpLst.size() - tmpLst.indexOf(lastInt);

                curTail = lastInt;

            }

            while (true) {

                Pos tmpPos = mp.get(curTail);

                if (empty || curTail > lastInt || tmpPos.len > curSize) {

                    List<Integer> inputLst = new ArrayList<>(tmpLst);

                    inputLst.add(curTail);

                    qe.offer(inputLst);

                    ret.add(inputLst);

                }

                if (tmpPos.pos + tmpPos.len >= nums.length) {

                    break;

                }

                curTail = nums[tmpPos.pos + tmpPos.len];

            }

        }

        return ret;

    }

}

public class Main {

    public static void main(String[] args) {

        System.out.println("Hello!");

        Solution solution = new Solution();

        int[] nums = {1,1,2,2,2};

        List<List<Integer>> ret = solution.subsetsWithDup(nums);

        System.out.printf("Get ret: %d\n", ret.size());

        Iterator<List<Integer>> iter = ret.iterator();

        while (iter.hasNext()) {

            Iterator itemItr = iter.next().iterator();

            while (itemItr.hasNext()) {

                System.out.printf("%d,", itemItr.next());

            }

            System.out.println();

        }

        System.out.println();

    }

}

// 这是之前的方法

class Solution {

public:

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        vector<vector<int>> result;

        sort(nums.begin(), nums.end());

        vector<int> tmp;

        result.push_back(tmp);

        int vlen;

        int is_dup = 0;

        vector<int> newtmp;

        int nlen = nums.size();

        for (int i = 0; i < nlen; i++) {

            if (i > 0 && nums[i] == nums[i-1]) {

                is_dup++;

            }

            else {

                is_dup = 0;

            }

            vlen = result.size();

            for (int j = 0; j < vlen; j++) {

                tmp = result[j];

                if (is_dup > 0 && \

                    (tmp.size() < is_dup || tmp[tmp.size()-is_dup] != nums[i])) {

                    // ignore dup

                    continue;

                }

                newtmp.resize(tmp.size());

                copy(tmp.begin(), tmp.end(), newtmp.begin());

                newtmp.push_back(nums[i]);

                result.push_back(newtmp);

            }

        }

        return result;

    }

};