f*********m
发帖数: 726 | 1 碰上类似的问题，除了用set,总是搞不定。谢谢指教。要排序和用prev吗？
Given a collection of integers that might contain duplicates, S, 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 S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
] | h*****3
发帖数: 1391 | 2 我觉的你要把leetcode上所有的题都问一遍。 | f*********m
发帖数: 726 | 3 没有搜到合适的答案，自己又不会做，能有什么别的办法呢？ | a**********2
发帖数: 340 | | f*********m
发帖数: 726 | 5 请问能show一下code吗？
非常感谢。
我写了一个，不过没有通过online judge.
void SubsetII(vector & I, int start, vector &A, vector
> &ret, int level) {
if(level == I.size()) {
ret.push_back(A);
return;
}
int i = start;
int prev = -1;
if (I[i] != prev) {
A.push_back(I[i]);
SubsetII(I, i + 1, A, ret, level + 1);
A.pop_back();
prev = I[i];
}
SubsetII(I, i + 1, A, ret, level + 1);
}
vector > subsetsWithDup(vector &S) {
vector > ret;
vector A;
sort(S.begin(), S.end());
SubsetII(S, 0, A, ret, 0);
return ret;
} | j********2
发帖数: 82 | 6 有人给个正解吗？
int>
【在 f*********m 的大作中提到】
: 请问能show一下code吗？
: 非常感谢。
: 我写了一个，不过没有通过online judge.
: void SubsetII(vector & I, int start, vector &A, vector
: > &ret, int level) {
: if(level == I.size()) {
: ret.push_back(A);
: return;
: }
: int i = start;
| a*******y
发帖数: 1040 | 7 why dont you just check if(find(ret.begin(), ret.end(), A) == ret.end()) and
then add into the vector
int>
【在 f*********m 的大作中提到】
: 请问能show一下code吗？
: 非常感谢。
: 我写了一个，不过没有通过online judge.
: void SubsetII(vector & I, int start, vector &A, vector
: > &ret, int level) {
: if(level == I.size()) {
: ret.push_back(A);
: return;
: }
: int i = start;
| e***s
发帖数: 799 | 8 Bad performance
and
【在 a*******y 的大作中提到】
: why dont you just check if(find(ret.begin(), ret.end(), A) == ret.end()) and
: then add into the vector
:
: int>
| R******1
发帖数: 58 | 9 刚写了一个可以work的，但是感觉效率很低
还是实现了一个find的function
class Solution {
public:
vector > subsetsWithDup(vector &S) {
vector myset = S;
sort (myset.begin(), myset.end());
return subset (myset);
}
vector< vector > subset (vector &S) {
vector < vector > res;
vector < vector > imediate;
vector < vector >::iterator it;
vector temp;
int lastdigit, pre;
if (S.size() == 1) {
res.insert(res.end(),temp);
temp.insert(temp.end(),S[0]);
res.insert(res.end(),temp);
return res;
}else if (S.size() > 1) {
lastdigit = S.back();
S.pop_back();
pre = S.back();
imediate = subset(S);
res = imediate;
if (pre != lastdigit){
for (it = imediate.begin(); it < imediate.end(); it++) {
temp = *it;
temp.insert(temp.end(),lastdigit);
res.insert(res.end(),temp);
}
}else{
for (it = imediate.begin(); it < imediate.end(); it++) {
temp = *it;
temp.insert(temp.end(),lastdigit);
if ( !vectorFind(res,temp) ){
res.insert(res.end(),temp);
}
}
}
}else{
return res;
}
}
bool vectorFind (vector < vector > &S, vector &target) {
vector< vector >::iterator it;
for (it = S.begin(); it < S.end(); ++it) {
if (*it == target) return true;
}
return false;
}
}; | j********2
发帖数: 82 | 10 这个是不是还是先产生解再检查是否已经产生过？正解应该是不产生重复解吧（就像
permutation的问题一样）
【在 R******1 的大作中提到】
: 刚写了一个可以work的，但是感觉效率很低
: 还是实现了一个find的function
: class Solution {
: public:
: vector > subsetsWithDup(vector &S) {
: vector myset = S;
: sort (myset.begin(), myset.end());
: return subset (myset);
: }
:
| | | R******1
发帖数: 58 | 11 对的 是在插入vector之前先检查是否产生过
开始是想不产生重复解的，但是程序是recursive的，混起来之后有点儿乱，就偷懒了
一下
有什么办法可以不用先生成再check的吗
【在 j********2 的大作中提到】
: 这个是不是还是先产生解再检查是否已经产生过？正解应该是不产生重复解吧（就像
: permutation的问题一样）
| p*****2
发帖数: 21240 | 12 我写了一个你看看对不对。好久没做题了，感觉有些生疏。
ArrayList> all = new ArrayList>();
void dfs(int[] num, int start, ArrayList al)
{
all.add(new ArrayList(al));
int prev=-1;
for(int i=start;i
{
if(num[i]!=prev)
{
al.add(num[i]);
dfs(num,i+1,al);
al.remove(al.size()-1);
prev=num[i];
}
}
}
public ArrayList> subsetsWithDup(int[] num)
{
all.clear();
Arrays.sort(num);
ArrayList al=new ArrayList();
dfs(num,0,al);
return all;
} | Y********f
发帖数: 410 | 13 这个是对的，该怎么理解呢？
);
【在 p*****2 的大作中提到】
: 我写了一个你看看对不对。好久没做题了，感觉有些生疏。
: ArrayList> all = new ArrayList>();
:
: void dfs(int[] num, int start, ArrayList al)
: {
: all.add(new ArrayList(al));
: int prev=-1;
: for(int i=start;i: {
: if(num[i]!=prev)
| p**v
发帖数: 853 | 14 我的思路是用一个类似于binary tree的图来做的，
开始时只有0 （empty set）， 然后左边不加新元素，右边加，
遇到重复就在现有set的基础上加1至cnt+1个，因为我这里的cnt
是从0开始的，程序中就是从0到cnt loop的。
希望能帮助你理解
vector > subsets2(vector &s) {
vector > results;
if (s.empty()) return results;
results.push_back(vector());//init with an empty set
int cnt;
sort(s.begin(), s.end());
for (size_t i=0; i
//compute this first because it will increase during the loop
size_t limit=results.size();
cnt=0;
while (i+cnt
cnt++;//compute how many dups
for (size_t sz=0; sz
vector v = results[sz];
for (int ii=0; ii<=cnt; ++ii) {
v.push_back(s[i]);
results.push_back(v);
}
}
}
return results;
}
all
【在 f*********m 的大作中提到】
: 碰上类似的问题，除了用set,总是搞不定。谢谢指教。要排序和用prev吗？
: Given a collection of integers that might contain duplicates, S, 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 S = [1,2,2], a solution is:
: [
: [2],
| H********e
发帖数: 130 | 15 我也贴一个我做的，大数据测试60ms
我的写了一个子函数，可以生成 大小为m的 subset，subset不会因为duplicate
element重复，然后主函数循环调用子函数
class Solution {
public:
vector > subsetsWithDup(vector &S) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > subsets;
if(S.size()==0)
return subsets;
sort(S.begin(),S.end());
int len=S.size();
int * a=new int[len];
for(int i=0;i
a[i]=S[i];
}
stack s;
for(int i=0;i<=len;i++){
subset(a,len,i,0,s, subsets);
}
return subsets;
}
void subset(int * a, int n, int m, int k, stack & s, vector
int> > &subsets){
if(m==0){
//save current subset
vector * curSubset = new vector();
while(!s.empty()){
curSubset->push_back(s.top());
s.pop();
}
int len=curSubset->size();
for(int i=len-1;i>=0;i--){
s.push(curSubset->at(i));
}
//make sure subset is non-descending order
sort(curSubset->begin(),curSubset->end());
subsets.push_back(*curSubset);
}
if(n - k +1 < m )
return;
for(int i=k;i
if(i > k && a[i]==a[i-1]){
continue;
}
s.push(a[i]);
subset(a,n,m-1,i+1, s, subsets);
s.pop();
}
}
};
这个题刚好是我选的一门课的作业题，老师给个参考答案：
一种是我这种 用stack帮助枚举，另一种解法就是二爷给的用DFS解
时间复杂度，子函数是O(m*Cnm),不可能做的更好了 | E****U
发帖数: 59 | 16 C++ iterative solution, 请指教:
class Solution {
public:
vector > subsetsWithDup(vector &S) {
vector v;
vector > result;
result.push_back(v);
sort(S.begin(), S.end());
int b = S[0] == 0 ? 1 : 0;
int begin = 0;
int size = 0;
for (int& a : S)
{
int i = (a == b) ? size : 0;
size = result.size();
for (; i < size; ++i)
{
v = result[i];
v.push_back(a);
result.push_back(v);
}
b = a;
}
return result;
}
}; | b*******e
发帖数: 217 | 17 Simply backtracking problem? Sure dfs ok for this kind of problem
在 flynewdream (fly) 的大作中提到: 】
all | b*******e
发帖数: 217 | 18 Simply backtracking problem
在 flynewdream (fly) 的大作中提到: 】
all |
|
