Generate all subsequences using recursion-CodePudding

Question: Given a string 's', generate all subsequences of the string using recursion. The output should be in a certain manner (all the subsequences of 'a' should be printed first, then subsequences of 'b' and so on and so forth).

The sample output for a given string 's' = abcd

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

I wasn't able to solve the problem in the first go but I took some help and then was able to solve it. Below is the code for it but what I am not able to get is that why we are passing i 1 in the recursion call and why not index 1? I tried doing it and obviously it was giving wrong output. I thought it is same as passing i 1 to it because either way the we are incrementing the index, right?

function allSubseq(new_str, str, index) {
  if (new_str.length !== 0) {
    console.log(new_str.join(""));
  }
  if (index === str.length) {
    return;
  }
  for (let i = index; i < str.length; i  ) {
    new_str.push(str[i]);
    allSubseq(new_str, str, i   1);
    new_str.pop(); // Backtracking step
  }
}

let str = "abcd";
new_str = [];
allSubseq(new_str, str, 0);

CodePudding user response：

Does this work as you expected? I just deleted i.

let str = "abcd";
let new_str = [];
function allSubseq(new_str, str, index) {
  if (new_str.length !== 0) {
    console.log(new_str.join(""));
  }
  if (index === str.length) {
    return;
  }
  for (; index < str.length; index  ) { // notice now we use index instead of i
    new_str.push(str[index]);
    allSubseq(new_str, str, index   1);
    new_str.pop(); // Backtracking step
  }
}

You probably should not use underscores in variable names unless it is a constant, and in that case it is written in capital case.

If you keep the i and just replace allSubseq(new_str, str, i 1); with allSubseq(new_str, str, index 1); then you still increment only i and not index that you pass to next call of allSubseq.

// we begin with the first call
function allSubseq(new_str, str, index) {
    if (new_str.length !== 0) {
        console.log(new_str.join(""));
    }
    if (index === str.length) {
        return;
    }
    // we begin first loop, here index is 0, i is 0.
    for (let i = index; i < str.length; i  ) {
        new_str.push(str[i]);
        // we call this function second time
        allSubseq(new_str, str, i   1);
        new_str.pop();
    }
}
// we call this function second time
// inside this scope index is 1
function allSubseq(new_str, str, index) {
    if (new_str.length !== 0) {
        console.log(new_str.join(""));
    }
    if (index === str.length) {
        return;
    }
    // we begin second loop, here index is 1, i is 1.
    for (let i = index; i < str.length; i  ) {
        new_str.push(str[i]);
        /* now lets pretend that this loop finished it's work with i and index as 1,
           let's also pretend that function exited without further recursion calls. */
        allSubseq(new_str, str, i   1);
        new_str.pop();
    }
}
// we come back to our first function call to the for loop
function allSubseq(new_str, str, index) {
    if (new_str.length !== 0) {
        console.log(new_str.join(""));
    }
    if (index === str.length) {
        return;
    }
    for (let i = index; i < str.length; i  ) {
        new_str.push(str[i]);
        allSubseq(new_str, str, i   1); /* <- we finished this step,
          inside that function call i and index were 1.
          we now come back to this for loop that we began,
          here index and i are still 0. */
        new_str.pop();
    }
    /* we will now update i to be i   1 (because of i   inside loop)
 and begin next step of loop where i will be a bigger number than it used to be on last step,
 however if we use index instead of i at `allSubseq(new_str, str, i   1);`,
 then we didn't update it (index) inside this loop and it will be the same number, on each step of the loop,
 it will only change inside recursion because we pass index   1. */
}