LeetCode: Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

---

The idea is same as generating subsets for set without duplicates. One more step is that after sorting the set, when the current element is equal to the previous element, we can skip this case to skip duplicate subsets.

C++ Code:

/*
 * func: subsets_duplicates_helper
 * goal: DFS helper function for generating subsets
 * @param subset: current subset generated
 * @param curr: current visiting index in S
 * @param S: input set S
 * @param result: result set
 * return:
 */
void subsets_duplicates_helper(vector<int> &subset, int curr, vector<int> &S, vector<vector<int> > &result){
    if(curr > S.size()){
        return;
    }
    result.emplace_back(subset);
    for(int i = curr; i < S.size(); ++i){
        if(i > curr && S[i] == S[i-1])
            continue;
        subset.emplace_back(S[i]);
        subsets_duplicates_helper(subset, i + 1, S, result);
        subset.pop_back();
    }
}

/*
 * func: subsets_duplicates
 * goal: create non-duplicate subsets
 * @param S: input set
 * return: the set of subsets
 */
vector<vector<int> > subsets_duplicates(vector<int> &S){
    sort(S.begin(), S.end());
    vector<vector<int> > result;
    vector<int> subset;
    
    subsets_duplicates_helper(subset, 0, S, result);
    return result;
}

Python Code:

# func: find all distinct subsets
# @param S: input set S
# @return: a list of all subsets
def subsets_duplicates(S):
    subset = []
    result = []
    S.sort()
    def subsets_duplicates_helper(curr):
        if curr > len(S):
            return

        result.append(subset[:])
        for i in xrange(curr, len(S)):
            if i > curr and S[i] == S[i-1]:
                continue
            subset.append(S[i])
            subsets_duplicates_helper(i + 1)
            subset.pop(-1)

    subsets_duplicates_helper(0)
    return result