题目:subsetsWithDup
要求:
给定一个可能具有重复数字的列表，返回其所有可能的子集 注意事项子集中的每个元素都是非降序的两个子集间的顺序是无关紧要的解集中不能包含重复子集样例:
如果 S = [1,2,2]，一个可能的答案为：[ [], [1], [1,2], [1,2,2], [2], [2,2]]算法要求:
你可以同时用递归与非递归的方式解决么？解题思路:
在17题的基础上改。算法如下:
bool isSame(vector<int> &v1, vector<int> &v2) { if (v1.size() != v2.size()) { return false; } sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); if (v1 == v2) { return true; } else { return false; } } vector<vector<int> > subsetsWithDup(const vector<int> &S) { // write your code here vector<vector<int> > vecs; bool has = false; int n = 1 << S.size(); int j = 0; int k = 0; for (int i = 0; i < n; i++) { j = i; k = 0; has = false; vector<int> vec; while (j) { if (j & 1) { // 这句话相当于j % 2 == 1 vec.push_back(S[k]); } j >>= 1; // 这句话相当于j /= 2; k++; } for (j = 0; j < vecs.size(); j++) { if (isSame(vecs[j], vec)) { has = true; break; } } if (!has) { vecs.push_back(vec); } } return vecs; }
