90. Subsets II

Problem

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution (Java)

class Solution {
    List<List<Integer>> allComb = new ArrayList<>();
    List<Integer> comb = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        dfs(0);
        allComb.add(new ArrayList<>());
        return allComb;
    }

    private void dfs(int start) {
        if (start > nums.length) {
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            comb.add(nums[i]);
            allComb.add(new ArrayList<>(comb));
            dfs(i + 1);
            comb.remove(comb.size() - 1);
        }
    }
}

Solution (Javascript)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
  var res = [];
  nums.sort((a, b) => a - b);
  helper(nums, 0, res, []);
  return res;
};

var helper = function (nums, start, res, now) {
  res.push(Array.from(now));

  for (var i = start; i < nums.length; i++) {
    if (i === start || nums[i] !== nums[i - 1]) {
      now.push(nums[i]);
      helper(nums, i + 1, res, now);
      now.pop();
    }
  }
};

Explain:

nope.

Complexity:

• Time complexity :
• Space complexity :