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],
  []
]

Challenge
Can you do it in both recursively and iteratively?

Link

Lintcode_ladder

Method

1. Recursion, normal combination template with de-dup
2. x

Example

1. Recursion

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsetsWithDup(const vector<int>& nums) {
        // write your code here
        vector<vector<int>> result;
        if (nums.empty()) {
            return result;
        }
        vector<int> row;
        vector<int> nums_copy(nums);
        int n = nums_copy.size();
        sort(nums_copy.begin(), nums_copy.end());
        helper(result, row, nums_copy, 0);
        return result;
    }
private:
    void helper(vector<vector<int>>& result, vector<int>& row, 
                vector<int>& nums, int start) {
        int n = nums.size();
        result.push_back(row);
        for (int i = start; i < n; ++i) {
            if (i != start && nums[i] == nums[i-1]) {
                continue;
            }
            row.push_back(nums[i]);
            helper(result, row, nums, i+1);
            row.erase(row.begin() + row.size() -1);
        }
        return;
    }
};

Similar problems

x

Tags

x