vector size remaining static after pushback() calls for powerset function

Question

I wrote the following function, as an implementation of this algorithm/approach, to generate the power-set (set of all subsets) of a given string:

vector<string> getAllSubsets(string a, vector<string> allSubsets) 
{   
    if(a.length() == 1)
    {   
    // Base case, 
    allSubsets.push_back("");
    allSubsets.push_back(a);
    }

    else {
        vector<string> temp = getAllSubsets(a.substr(0,a.length()-1),allSubsets);
        vector<string> with_n = temp;
        vector<string> without_n = temp;
        for(int i = 0;i < temp.size()-1;i++) 
        {
            allSubsets.push_back(with_n[i] + a[a.length()-1]);
            allSubsets.push_back(without_n[i]);
        }
    }
    return allSubsets;

}

however, someone appears to be going wrong: the size of temp and allSubsets remains static from recursive call to recursive call, when they should be increasing due to the push_back() calls. is there any reason why this would take place?

Change the argument `allSubsets` to be passed by reference instead of by value. Use `vector& allSubsets`. — R Sahu, Mar 25 '15 at 20:37
That is not the problem, as he returns his changes to allSubsets and then pushes back into his local allSubsets. His value should be included. — Puppy, Mar 25 '15 at 20:45
There seem to be a number of different issues with this. The correct answer will need to deal with all of them. Be patient before answering! Frankly, I'm a bit confused by the whole design; shouldn't getAllSubsets simply take one parameter, the string? — Aaron McDaid, Mar 25 '15 at 20:59

score 3 · Accepted Answer · answered Mar 25 '15 at 20:48

It's because you have an off-by-one error. Because this occurs in your next-to-base case, you are never inserting any entries.

Since the first invalid index is temp.size(), i < temp.size() means that you will always have a valid index. Subtracting 1 means that you are missing the last element of the vector.

It's worth noting that passing allSubsets in as a parameter is kinda silly because it's always empty. This kind of algorithm simply doesn't require a second parameter. And secondly, you could be more efficient using hash sets that can perform deduplication for you simply and quickly.

Upvoted your answer and deleted my answer. Good catch! – tourniquet_grab Mar 25 '15 at 20:57 — tourniquet_grab, Mar 25 '15 at 20:57

vector size remaining static after pushback() calls for powerset function

1 Answers1