where i am wrong in given program?

Question

Here is my program to find all the subsets of given set. To solve it, I used recursion. But when I compiled it in windows on codeblocks. It gives

This application has requested the Runtime to terminate it in a unusual way.

and in gcc compiler it didn't show any answer, no response.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> findAllSubset(char c, vector<string> v) {
    int size = v.size();
    if(size == 1) {
        v.push_back("");
        return v;
    }
    c = v[size-1][0];
    v.pop_back();
    v = findAllSubset(c, v);

    for(int i = 0; i < v.size(); i++) {
        string s= "";
        if(v[i].size() == 0){
            s += c;
            v.push_back(s);
        }
        else {
            s += v[i] + c;
            v.push_back( s );
        }
    }
    return v;
}

main() {
    vector<string> v, ans;
    char c = 65;
    v.push_back("a");
    v.push_back("b");
    //v.push_back("c");
    //v.push_back("d");
    ans = findAllSubset(c, v);
    return 0;
}

By using **reference**. Also, if you really mean set, there's `std::set<>` container. I didn't really understand your algorithm there, but certainly your usage of standard library is inefficient. — Bartek Banachewicz, Jun 12 '12 at 09:58
First, it's "vector", not "set"; second, by reference, of course. @nhahtdh, I don't know what you mean, but you obviously can push `const char *` into `vector`... — Griwes, Jun 12 '12 at 09:59
The first problem here is that the program flow in the function is far from obvious. Even without bugs this would be a nightmare to maintain. Your first step should be to make the logic obvious – both in your head, and then translated into code. This will probably also clear up the error. — Konrad Rudolph, Jun 12 '12 at 09:59
@BartekBanachewicz, it's not called STL, m'kay? http://stackoverflow.com/questions/5205491/whats-this-stl-vs-c-standard-library-fight-all-about/5205571#5205571 — Griwes, Jun 12 '12 at 10:00
As a note, I don't really understand how should your algorithm work; you have problem at algorithm level, not at source level. — Griwes, Jun 12 '12 at 10:04
How can you do `c = v[size-1][0];` on a vector? What does this mean? And it seems there is an infinite loop in your function `findAllSubset` — Sanish, Jun 12 '12 at 10:08
@Sanish: That'll be the first character of the (size-1)th string. — RobH, Jun 12 '12 at 10:29
Is there any other way to improve this algorithm? (To decrease time coplexity) — devsda, Jun 12 '12 at 11:22

score 5 · Accepted Answer · answered Jun 12 '12 at 10:13

5

The for loop is an infinite loop, each time an element is push_back in the vector, vector size increases making the condition i < v.size() is always true.

answered Jun 12 '12 at 10:13

learning

94
6

score 2 · Answer 2 · edited Jun 12 '12 at 10:03

2

You keep pushing strings to your vector while you loop through it. There is the infinite loop. It is generally a bad idea to alter a container while looping through it.

edited Jun 12 '12 at 10:03

Henrik

23,186
6
42
92

answered Jun 12 '12 at 10:01

steffen

8,572
11
52
90

Well, if he had some kind of assertion when to finish the loop, his loop would be perfectly valid, as he uses indices, not iterators, and only adds elements into his vector. But yup, the problem is that there is no such assertion. – Griwes Jun 12 '12 at 10:02

score 1 · Answer 3 · answered Jun 12 '12 at 09:55

1

There seems to be an infinite loop. The program compiles and runs normally but never exits

answered Jun 12 '12 at 09:55

karka91

733
1
6
20

where i am wrong in given program?

3 Answers3