Very simple and fast java solution


  • 40
    H
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> each = new ArrayList<>();
        helper(res, each, 0, nums);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> each, int pos, int[] n) {
        if (pos <= n.length) {
            res.add(each);
        }
        int i = pos;
        while (i < n.length) {
            each.add(n[i]);
            helper(res, new ArrayList<>(each), i + 1, n);
            each.remove(each.size() - 1);
            i++;
            while (i < n.length && n[i] == n[i - 1]) {i++;}
        }
        return;
    }
    

    The Basic idea is: use "while (i < n.length && n[i] == n[i - 1]) {i++;}" to avoid the duplicate. For example, the input is 2 2 2 3 4. Consider the helper function. The process is:

    • each.add(n[i]); --> add first 2 (index 0)
    • helper(res, new ArrayList<>(each), i + 1, n); --> go to recursion part, list each is <2 (index 0)>
    • while (i < n.length && n[i] == n[i - 1]) {i++;} --> after this, i == 3, add the element as in subset I

  • 0
    Y

    hi, hello_today_ , could you explain the intuition of your code? especially about the two i++ and how you avoid generate duplicates? thanks!


  • 0
    H

    I added some explanation, but not sure if they are clear. You can try some examples, like 2 2 2 3 4. It would be easy to understand.


  • 17

    @hello_today_ I come up with a similar solution like yours, and mine is more concise and standard, please check it out.

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            subsetsWithDupHelper(nums, 0, res, new ArrayList<>());
            return res;
        }
        
        private void subsetsWithDupHelper(int[] nums, int pos, List<List<Integer>> res, List<Integer> tmpRes) {
            // subset means it does not need contain all elements, so the condition is <= rather than ==
            // and do not return after this statement
            if(pos <= nums.length) res.add(new ArrayList<>(tmpRes));
            
            for(int i=pos; i<nums.length; i++) {
                if(i > pos && nums[i] == nums[i-1]) continue;   // avoid duplicates
                tmpRes.add(nums[i]);
                subsetsWithDupHelper(nums, i + 1, res, tmpRes);
                tmpRes.remove(tmpRes.size() - 1);
            }
        }
    }
    

  • 0
    C

    @xietao0221 really nice and clean solution. Thank you! One small thing I'm concerned with both of these solutions is wouldn't Arrays.sort change the original array? maybe that's fine but maybe the order of the array is important before passing it to the function.


  • 0

    @crgores Subset doesn't care about the order, and the reason why we do the sorting first is to avoid duplicates.


  • 1
    C

    @xietao0221 right, it makes sense why you need to sort, but if someone were to use this function and assume their array wouldn't be changed, they would wrong. It's a trivial change I guess, just make a copy of the array and sort.


  • 0

    @crgores You are right, we'd better not modify the input data in the real world. Thank you for sharing this point.


  • 2
    R

    Could anyone explain the time and space complexity?


  • 0
    D

    @rowena000 Correct me if I'm wrong. Space complexity is O(n), Time complexity is O(n*2^n).


Log in to reply
 

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