Subsets II

Description

Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice

• Each element in a subset must be in _non-descending _order.
• The ordering between two subsets is free.
• The solution set must not contain duplicate subsets.

Example

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

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

Clarification

Do I need to implement KMP Algorithm in a real interview?

• Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first

Challenge

Can you do it in both recursively and iteratively?

Related problems

Subsets

Implementation

Link: http://lintcode.com/en/problem/subsets-ii

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(const vector<int> &S) {
        // write your code here
        vector<vector<int> > ret;
        vector<int> path;
        int step = 0;
        vector<int> s = S;

        sort(s.begin(), s.end());

        helper(ret, path, s, step);
        return ret;
    }

    void helper(vector<vector<int> > & ret, vector<int> & path, const vector<int> &s, int step){
        ret.push_back(path);

        if(step == s.size()) return;

        for(int i = step; i < s.size(); i++){
            if(i != step && s[i] == s[i - 1]) continue;
            path.push_back(s[i]);
            helper(ret, path, s, i + 1);
            path.pop_back();
        }
    }
};