90

90. Subsets II (Medium)

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

Companies: Amazon, Bloomberg, Yahoo

Related Topics:
Array, Backtracking, Bit Manipulation

Similar Questions:

• Subsets (Medium)
• Find Array Given Subset Sums (Hard)

Solution 1. DFS

Consider how duplicates are generated.

Say A = [2,2], let use[i] = 1 or 0 mean whether we use A[i].

• use=[1,1], subset=[2,2]
• use=[1,0], subset=[2,x]
• use=[0,1], subset=[x,2]. Duplication happens here. The pattern is that, if we don't use A[i], we shouldn't use any subsequent A[j] == A[i] (j > i).
• use=[0,0], subset=[x,x]

// OJ: https://leetcode.com/problems/subsets-ii/
// Author: github.com/lzl124631x
// Time: O(N^2 * 2^N)
// Space: O(N)
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& A) {
        sort(begin(A), end(A));
        vector<vector<int>> ans;
        vector<int> tmp;
        int N = A.size();
        function<void(int)> dfs = [&](int i) { // dfs(i) tries using and not using A[i]
            if (i == N) {
                ans.push_back(tmp);
                return;
            }
            // use A[i]
            tmp.push_back(A[i]);
            dfs(i + 1);
            tmp.pop_back();
            // skip A[i]. When A[i] is skipped, we shouldn't use any `A[j] == A[i] (j > i)` because that will cause duplication. We need to skip subsequent same characters and start with a different character.
            while (i + 1 < N && A[i + 1] == A[i]) ++i;
            dfs(i + 1);
        };
        dfs(0);
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/subsets-ii/
// Author: github.com/lzl124631x
// Time: O(N^2 * 2^N)
// Space: O(N)
class Solution {
private:
public:
    vector<vector<int>> subsetsWithDup(vector<int>& A) {
        sort(begin(A), end(A));
        vector<vector<int>> ans;
        vector<int> tmp;
        int N = A.size();
        function<void(int, int)> dfs = [&](int start, int len) {
            if (!len) {
                ans.push_back(tmp);
                return;
            }
            for (int i = start; i <= N - len; ++i) {
                if (i != start && A[i] == A[i - 1]) continue;
                tmp.push_back(A[i]);
                dfs(i + 1, len - 1);
                tmp.pop_back();
            }
        };
        for (int len = 0; len <= N; ++len) dfs(0, len);
        return ans;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/subsets-ii/
// Author: github.com/lzl124631x
// Time: O(N^2 * 2^N)
// Space: O(N)
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans(1);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ) {
            int cnt = 0, n = nums[i], len = ans.size();
            while (i < nums.size() && nums[i] == n) ++cnt, ++i;
            for (int j = 0; j < len; ++j) {
                vector<int> sub = ans[j];
                for (int k = 0; k < cnt; ++k) {
                    sub.push_back(n);
                    ans.push_back(sub);
                }
            }
        }
        return ans;
    }
};