Question

Formatted question description: https://leetcode.ca/all/90.html

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10

Algorithm

Take the example [1 2 2] in the title for analysis. According to the analysis in Subsets before, when the first 2 is processed, the subsets at this time are [], [1], [2], [1, 2], and when processing the second 2 at this time, if you add 2 directly after [] and [1], there will be duplication, so you can only add 2 after the last two subsets generated by the previous loop.

We use last to record the last processed number, and then determine whether the current number is the same as the above.

If it is different, the loop will continue from 0 to the number of the current subset.
If the same, then The number of new subsets minus the number of subsets in the previous loop is used as the starting point to loop, so that there will be no duplication

My solving process:

nums = [1,2,2,2]
[],1,	2,12,	2,12,22,122,	2,12,22,122,22,122,222,1222

from above, every time the new add is doubled, count: 1,2,4,8 so, the 1st half is duplicated, and 2nd half is NOT duplicated so, when going into a new loop, append duplicated num to ONLY 2nd half elements

then:

[],1

append 2, not duplicated, append as normal:

[],1,	2, 12

append 2, same as previous 2, then append last 2 elements - “2,12”

[],1,	2, 12,		22,122

append 2, same as previous 2, then append last 2 elements - “22,122”

[],1,	2, 12,		22,122,		222,1222

append 2, same as previous 2, then append last 2 elements - “222,1222”

[],1,	2, 12,		22,122,		222,1222,		2222,12222

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets_II {

    public static void main(String[] args) {
        Subsets_II out = new Subsets_II();
        Solution s = out.new Solution();

        for (List<Integer> each : s.subsetsWithDup(new int[]{1, 1})) {
            System.out.println(each.toString());
        }
    }

    class Solution_better {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            backtrack(0, nums, new ArrayList<>(), res);
            return res;
        }

        private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> res) {
            res.add(new ArrayList<>(path));
            for (int i = start; i < nums.length; i++) {
                if (i > start && nums[i] == nums[i-1]) { // key is i>start, so it covers input=[1,5,5]
                    continue;
                }
                path.add(nums[i]);
                backtrack(i+1, nums, path, res);
                path.remove(path.size() - 1);
            }
        }
    }


    class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            if (nums == null || nums.length == 0) {
                return list;
            }

            Arrays.sort(nums); // requirement: non-descending order

            // prepare, add empty one to start looping then.
            // @note: I forgot empty
            ArrayList<Integer> empty = new ArrayList<>();
            list.add(empty);

            int prevIndex = 0;

            for (int i = 0; i < nums.length; i++) {
                int numToAdd = nums[i];
                List<List<Integer>> newlyAddedList = new ArrayList<>(list);

                int start = (i > 0 && nums[i] == nums[i - 1]) ? prevIndex : 0;

                for (int j = start; j < list.size(); j++) {
                    List<Integer> each = list.get(j);
                    ArrayList<Integer> newOne = new ArrayList<Integer>(each); // deep copy

                    newOne.add(numToAdd);
                    newlyAddedList.add(newOne);

                }

                prevIndex = list.size();
                list = newlyAddedList;
            }

            return list;
        }
    }
}

############

class Solution {
    private List<List<Integer>> ans;
    private int[] nums;

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

    private void dfs(int u, List<Integer> t) {
        ans.add(new ArrayList<>(t));
        for (int i = u; i < nums.length; ++i) {
            if (i != u && nums[i] == nums[i - 1]) {
                continue;
            }
            t.add(nums[i]);
            dfs(i + 1, t);
            t.remove(t.size() - 1);
        }
    }
}

// OJ: https://leetcode.com/problems/subsets-ii/
// Time: O(2^N * N^2)
// Space: O(2^N * N)
class Solution {
    set<vector<int>> s;
    vector<int> tmp;
    void dfs(vector<int> &A, int i) {
        if (i == A.size()) {
            s.insert(tmp);
            return;
        }
        dfs(A, i + 1);
        tmp.push_back(A[i]);
        dfs(A, i + 1);
        tmp.pop_back();
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& A) {
        sort(begin(A), end(A));
        dfs(A, 0);
        return vector<vector<int>>(begin(s), end(s));
    }
};

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(u, t):
            ans.append(t[:]) # or, t.copy()
            for i in range(u, len(nums)):
                 # also good for [1,5,5], second '5' will be skipped here if
                 # but second '5' is always covered, because i==u when ans=[1,5] and i=2
                if i != u and nums[i] == nums[i - 1]:
                    continue
                t.append(nums[i])
                dfs(i + 1, t)
                t.pop()

        ans = []
        nums.sort()
        dfs(0, [])
        return ans


# iteration
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # requirement: non-descending order
        res = [[]]
        prev_index = 0
        
        for i in range(len(nums)):
            num_to_add = nums[i]
            newly_added_list = res.copy()
            
            start = prev_index if (i > 0 and nums[i] == nums[i - 1]) else 0
            
            for j in range(start, len(res)):
                each = res[j]
                new_one = each.copy() # deep copy
                new_one.append(num_to_add)
                newly_added_list.append(new_one)

            prev_index = len(res)
            res = newly_added_list

        return res

############

class Solution(object):
  def subsetsWithDup(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """

    def dfs(start, nums, path, res, visited):
      res.append(path + [])

      for i in range(start, len(nums)):
        if start != i and nums[i] == nums[i - 1]:
          continue
        if i not in visited:
          visited[i] = 1
          path.append(nums[i])
          dfs(i + 1, nums, path, res, visited)
          path.pop()
          del visited[i]

    nums.sort()
    res = []
    visited = {}
    dfs(0, nums, [], res, visited)
    return res

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	var ans [][]int
	var dfs func(u int, t []int)
	dfs = func(u int, t []int) {
		ans = append(ans, append([]int(nil), t...))
		for i := u; i < len(nums); i++ {
			if i != u && nums[i] == nums[i-1] {
				continue
			}
			t = append(t, nums[i])
			dfs(i+1, t)
			t = t[:len(t)-1]
		}
	}
	var t []int
	dfs(0, t)
	return ans
}

function subsetsWithDup(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const t: number[] = [];
    const res: number[][] = [];
    const dfs = (i: number) => {
        if (i === n) {
            res.push([...t]);
            return;
        }
        t.push(nums[i]);
        dfs(i + 1);
        const num = t.pop();
        while (i < n && nums[i] == num) {
            i++;
        }
        dfs(i);
    };
    dfs(0);
    return res;
}

impl Solution {
    fn dfs(mut i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
        let n = nums.len();
        if i == n {
            res.push(t.clone());
            return;
        }
        t.push(nums[i]);
        Self::dfs(i + 1, t, res, nums);
        let num = t.pop().unwrap();
        while i < n && num == nums[i] {
            i += 1;
        }
        Self::dfs(i, t, res, nums);
    }

    pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort();
        let mut res = Vec::new();
        Self::dfs(0, &mut Vec::new(), &mut res, &nums);
        res
    }
}

90 - Subsets II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions