90. Subsets II

Leetcode Array Backtracking

题目

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

分析

这道题目与Leetcode 78. Subsets的唯一不同点为给的整数有可能出现重复。其实和40. Combination Sum II、47. Permutations II的处理技巧相同：先排序，然后直接跳过重复的元素。

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &nums) {
        vector<vector<int> > res;
        vector<int> vec;
        sort(nums.begin(), nums.end());
        subsetsWithDupHelper(res, nums, nums.size(), vec, 0);
        return res;
    }
private:
    void subsetsWithDupHelper(vector<vector<int> > &res, vector<int> &nums, int n, vector<int> &vec, int position) {
        res.push_back(vec);
        for (int i = position; i < n; ++i) {
            if ((i>position)&&(nums[i]==nums[i-1])){
                continue;
            } else{
                vec.push_back(nums[i]);
                subsetsWithDupHelper(res, nums, n, vec, i + 1);
                vec.pop_back();
            }
        }
    }
};