Accepted java iterative solution

  • 10

    for explanation plz see comments in the code

    public List<List<Integer>> subsetsWithDup(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int len = num.length;
        if (len == 0) return ans; 
        ans.add(new ArrayList<Integer>()); // first, need to add the subset of num[0]
        ans.add(new ArrayList<Integer>());
        int nprev = 1; // this is the number of lists that the previous number was added in.
                     // if the current number is same as the prev one, it'll be only added in the 
                    // lists that has the prev number.
        for (int i = 1; i < len ; ++i){
            int size = ans.size();
            if (num[i]!=num[i-1])   // if different
                nprev = size;        // this means add num[i] to all lists in ans;
            for (int j = size-nprev; j < size; ++j){
                List<Integer> l = new ArrayList<Integer>(ans.get(j));
        return ans;

  • 0

    Great idea! I was impressed!!!

  • 0


    It took me 1 nearly an hour to understand the algorithm. And I learnt a lot.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.