Subsets II

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

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

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

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

Discussion

会根据Permutation扩展Permutation II的话这题就一点都不难，根据Subsets的第二个solution扩展。

Solution

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(vector<int> &nums) {
        // write your code here
        //vector<int> nums = S;
        sort(nums.begin(), nums.end());
        vector<vector<int> > result;
        if(nums.size() == 0) return result;
        vector<int> solution(nums.size(), 0);
        backtracing(nums, 0, 0, solution, result);
        return result;
    }
private:
    void backtracing(vector<int> &nums, int dim, int start, 
        vector<int> &solution, vector<vector<int> > &records) {
        vector<int> subset;
        for(int i=0; i<dim; i++) {
            subset.push_back(solution[i]);
        }
        records.push_back(subset);
        int  lastnum = nums[0]-1;
        for(int i = start; i<nums.size(); i++) {
            if(nums[i] == lastnum)
                continue;//只是多了这个条件，如果当前的值跟上次一样，就没有必要再放到该维度上了。
            lastnum = nums[i];
            solution[dim] = nums[i];
            backtracing(nums, dim+1, i+1, solution, records);
        }
    }
};

Solution

DFS solution.

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(vector<int> &nums) {
        // write your code here
        vector<vector<int> > result;
        int n = nums.size();
        if(n==0) return result;
        vector<int> solution;
        sort(nums.begin(), nums.end());
        dfs(nums, result, solution, 0);
        return result;
    }
private:
    void dfs(vector<int> nums, vector<vector<int> > &result, vector<int> solution,
        int pos) {
            int n = nums.size();
            result.push_back(solution);
            for(int i=pos; i<n; i++) {
                if(i!=pos && nums[i-1] == nums[i])
                    continue;//跟subset问题相比多了这个判断条件
                solution.push_back(nums[i]);
                dfs(nums, result, solution, i+1);
                solution.pop_back();
            }
        }
};

迭代的方法。向量递增法的扩展，新元素要么是不重复的，要么是增加到新扩展的subset上。

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int> > result(1);
        sort(S.begin(), S.end());
        size_t previous_size = 0;
        for(size_t i=0; i < S.size(); i++) {
            const size_t size = result.size();
            for(size_t j = 0; j< size; j++) {
                // only union non-duplicate element or new union set
                if(i==0 || S[i] != S[i-1] || j>=previous_size) {
                    result.emplace_back(result[j]);
                    result.back().emplace_back(S[i]);
                }
            }
            previous_size = size;
        }
        return result;

    }
};