Subsets II

發表於   |   分類於

LeetCode: Subsets II

Given a collection of integers that might contain duplicates, nums, 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 nums = [1,2,2], a solution is:

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

从一个集合生成它的子集，要求所有子集元素非递减排序，不能有重复的子集。

使用增量法生成子集（增量法是一个回溯算法），在此过程中判断集合是否重复。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:

    vector<vector<int>> result;

    bool isVectorEqual(vector<int>& l,vector<int>& r)
    {
        if (l.size() != r.size())
        {
            return false;
        }
        else
        {
            for(int i = 0 ; i < l.size(); ++i)
            {
                if (l[i] != r[i])
                {
                    return false;
                }
            }
        }
        return true;
    }

    // 增量生成子集
    void subsets(vector<int>& nums, int begin, vector<int>& v)
    {
        for(int i = begin; i < nums.size(); ++i)
        {
            v.push_back(nums[i]);
            bool exist = false;
            // 判断是否有重复的
            for(int j = 0 ; j < result.size(); ++j)
            {
                if (isVectorEqual(result[j],v))
                {
                    exist = true;
                }
            }
            if (!exist)
            {
                result.push_back(v);
            }
            subsets(nums,i+1,v);
        }
        v.pop_back(); // 回溯
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());// 不排序是无法得到正确输出的
        vector<int> prefix;
        result.push_back(prefix);// 空集显然放在首位
        subsets(nums,0,prefix);
        return result;
    }
};