Behaviour of array during recursion

Question

#include <iostream>
#include <vector>
using namespace std;
int count;
vector<char*> ans;
char result[1000];   //result will store the current subsequence
void printAllSubsequences(char str[], int beg, int res_index) {
    if(str[beg] == '\0') {  // if you reach end of string, print the result(i.e.,one of the subsequences). Recursion quits after encountering the last element in the given string str
        result[res_index] = '\0';
        ++count;
        cout<<result<<' ';
        ans.push_back(result);
        return;
    }

    printAllSubsequences(str, beg+1, res_index);
    result[res_index] = str[beg];
    printAllSubsequences(str, beg+1, res_index+1);
}
int main() {
    char str[1000];   //str is the string whose permutations we have to find
    cin >> str;
    char result[1000];
    printAllSubsequences(str, 0, 0);
    cout<<count<<endl;
    for(vector<char*>::iterator ii = ans.begin(); ii!=ans.end(); ++ii){
        cout<<(*ii)<<' ';
    }
    cout<<endl;
}

When I give an input as

abcd

I get the following as output

 d c cd b bd bc bcd a ad ac acd ab abd abc abcd 16
 abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd abcd

So, the first line returns the subsequences; great! For, the second if I store the same in a vector and then try to print it out, it gives me the same string over and over again. Where could the implementation be possibly going wrong ?

Thanks.

@Aryan vector<char*> ans; -- One of the worst code smells in C++. Unless you have a compelling reason (yes there are reasons, but not anything for what you're trying to achieve) , use vector<std::string>.. — PaulMcKenzie
– PaulMcKenzie, Commented Jul 7, 2017 at 19:23

Hemant Gangwar · Accepted Answer · 2017-07-07 19:13:59Z

2

Where could the implementation be possibly going wrong?

Here:

vector<char*> ans;

Explanation: You have created a vector of a pointer. Since every time you push the same pointer in the array so once the pointed memory output gets changed it will change the output of already pushed entries as well.

To fix the issue use std::string instead of char array

answered Jul 7, 2017 at 19:13

Hemant Gangwar

2,29218 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Behaviour of array during recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related