My accepted Java solution


  • 1
    D

    The idea is to maintain a separate list of subsets, newList, to keep track of all the newly added subsets at the last step in the for loop. If num[i] == num[i - 1], we don't want to append num[i] to all existing subsets but just to the ones that just got added last round to prevent duplication.

    For example, we have num to be {1, 2, 2}

    1. For {1}, we have subsets {{ }, {1}}.
    2. For {1, 2}, we have subsets{{ }, {1}, {2}, {1, 2}}. We just add {2} and {1, 2} to the subsets. So newList is {{2}, {1, 2}}.
    3. For {1, 2, 2}, since 2 == 2, we only append 2 to {2} and {1, 2} in newList respectively, which gives us a new newList {{2, 2}, {1, 2, 2}}, and then we add all to the subsets, so the result is {{ }, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}}.

    Please comment if you see something wrong or can be improved. Cheers!

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] num) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<Integer> subset = new ArrayList<Integer>();
            result.add(subset);
            
            if (num.length == 0) {
                return result;
            }
            
            Arrays.sort(num);
            
            List<List<Integer>> newList = new ArrayList<List<Integer>>();
            subset = new ArrayList<Integer>();
            subset.add(num[0]);
            newList.add(subset);
            result.add(subset);
            for (int i = 1; i < num.length; i++) {
                if (num[i] == num[i - 1]) {
                    List<List<Integer>> nextList = new ArrayList<List<Integer>>();
                    for (List<Integer> li : newList) {
                        subset = new ArrayList<Integer>(li);
                        subset.add(num[i]);
                        nextList.add(subset);
                    }
                    newList = nextList;
                    result.addAll(newList);
                }
                else {
                    newList.clear();
                    for (List<Integer> li : result) {
                        subset = new ArrayList<Integer>(li);
                        subset.add(num[i]);
                        newList.add(subset);
                    }
                    result.addAll(newList);
                }
            }
            return result;
        }
    }

  • 0
    W

    How about using a HashSet and then convert it to List?


  • 0
    H

    Using hashSet is the first idea i come up with but it seems to be a waste of space.


  • 0
    F

    yes, this solution is better than use hashset, have save a lot of space


  • 0
    F

    have two questions. 1st: when do you add{} to subset? 2nd: ex, if we have {0,1}, so expected output will be {{},{0},{1},{0,1}}. But in the for loop especially else part for this example, I think it only add{1} to the result list, where is part of code of adding {0,1}?? Since for loop only loop 1 time(i=1,num size is 2),so I cant find the part that adding {0,1} to the subset. Can you give me some idea about it? Thanks


  • 0
    H

    You can also use .contains() instead of HashSet


Log in to reply
 

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