I am trying to implement a method to get all subset of a set. I understand the logic of doing that. i.e. Subset(n) = n + Subset(n-1), but the code I wrote keep printing out the wrong answers. Here is my code:
void subset(vector<int> &input, vector<int> output, int current) {
if (current == input.size()-1) {
output.push_back(input[current]);
print(output);
}
else {
for (int i = current; i < input.size();i++) {
output.push_back(input[i]);
print(output);
subset(input, output, i+1);
}
}
}
Here is the output I got (input is {1,2,3}):
1
1 2
1 2 3
1 2 3
1 2
1 2 3
1 2 3
Any idea where I went wrong? Any help will be appreciated!
I think this can help you:
void subset(vector<int> &input, vector<int> output, int current) {
static int n=0;
if (current == input.size()) {
cout<<n++<<":\t {";
for(int i=0;i<output.size();i++) cout<<output[i]<<", ";
cout<<"\b\b}\n";
}
else {
subset(input, output, current+1); //exclude current'th item
output.push_back(input[current]);
subset(input, output, current+1); //include current'th item
}
}
and first time you may call it like this:
int main()
{
std::vector<int> inp, out;
for(int i=0; i<5; i++) // for example {1,2,3,4,5}
inp.push_back(i);
subset(inp, out, 0);
return 0;
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments