0

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);
heartbeat
  • 41
  • 1
  • 7
  • 2
    Why do you think that we increment index? `i++` not index, `let i = index` here `index` is scalar value (a number) so it is passed as value (if index was an object then it would be passed by reference and in that case `i` would get same reference and then mutating `i` would mutate `index`). – link2name Oct 23 '22 at 06:44

2 Answers2

1

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. */
}
link2name
  • 121
  • 7
  • Yes it's working as expected but am still confused as to what was happening in the first code? What was happening when I was passing index+1 instead of i+1 and why wasn't it working? – heartbeat Oct 23 '22 at 07:36
  • It would be nice if you would post your code with that change. If *all* you did was at line: `allSubseq(new_str, str, i + 1);` replace `i` to `index` then the problem is that you pass index + 1 but increment i. – link2name Oct 23 '22 at 07:48
  • 1
    You can think of this function as having two loops, one loop is for such task: first loop is for adding the next character to the end of string (like given 'ab' you get 'abc'), the other loop given a string goes over each character of the string and runs the first loop. – link2name Oct 23 '22 at 07:58
  • If you don't increment index inside for loop, then when you call `allSubseq(new_str, str, index + 1);` at each step of the for loop `index + 1` will be the same number. – link2name Oct 23 '22 at 08:03
  • 1
    So `i++` is used to step in first loop, and `index + 1` is used to step in second (recursion). But it is important that both of them are the same value, if you do `I was passing index+1 instead of i+1` then you still increment i (inside for loop), but you do not increment index. – link2name Oct 23 '22 at 08:06
  • Okay. So, you are saying index+1 won't gonna increment index but why not I mean it's getting passed as an argument to index? And, secondly how doing i+1 is incrementing the index? – heartbeat Oct 23 '22 at 08:57
  • Two loops, inside one we use i, that is the for loop, we increment it using `i++`, the other "loop" (actually recursion) uses index, and index is updated by calling function with `i+ 1`. now when you call `allSubseq(new_str, str, i + 1);`. The recursive "loop" will call this function with index updated to be 1 number higher. However we called this function from insides of the for loop and when our function will be done with it's work we will come back to our for loop, after we came back we do .pop and resume for loop with `i` updated because of `i++`. – link2name Oct 23 '22 at 09:02
  • 1
    So on the next step, i is one number higher. If we call `allSubseq(new_str, str, index + 1);` then we will call this function, inside this function index will be one number higher, we do our work, come back to for loop that called this function, do the `.pop`, and coninue our loop with `i++`, we are again at a step where we call `allSubseq(new_str, str, index + 1);` and here `index + 1` will be the same number as it was last time, because we did increment i and not index. – link2name Oct 23 '22 at 09:08
1

There are at least two good ways to analyze this question. The first is to fire up a debugger.1 This is often the best way. But you can also add logging to track what's happening. Here are the results of adding logging 2, using the shorter input "abc", first for

i + 1

allSubseq ([], "abc", 0)
    allSubseq ([a], "abc", 1)
    > console .log ("a")
        allSubseq ([a,b], "abc", 2)
        > console .log ("ab")
            allSubseq ([a,b,c], "abc", 3)
            > console .log ("abc")
        allSubseq ([a,c], "abc", 3)
        > console .log ("ac")
    allSubseq ([b], "abc", 2)
    > console .log ("b")
        allSubseq ([b,c], "abc", 3)
        > console .log ("bc")
    allSubseq ([c], "abc", 3)
    > console .log ("c")

and then for

index + 1

allSubseq ([], "abc", 0)
    allSubseq ([a], "abc", 1)
    > console .log ("a")
        allSubseq ([a,b], "abc", 2)
        > console .log ("ab")
            allSubseq ([a,b,c], "abc", 3)
            > console .log ("abc")
        allSubseq ([a,c], "abc", 2)
        > console .log ("ac")
            allSubseq ([a,c,c], "abc", 3)
            > console .log ("acc")
    allSubseq ([b], "abc", 1)
    > console .log ("b")
        allSubseq ([b,b], "abc", 2)
        > console .log ("bb")
            allSubseq ([b,b,c], "abc", 3)
            > console .log ("bbc")
        allSubseq ([b,c], "abc", 2)
        > console .log ("bc")
            allSubseq ([b,c,c], "abc", 3)
            > console .log ("bcc")
    allSubseq ([c], "abc", 1)
    > console .log ("c")
        allSubseq ([c,b], "abc", 2)
        > console .log ("cb")
            allSubseq ([c,b,c], "abc", 3)
            > console .log ("cbc")
        allSubseq ([c,c], "abc", 2)
        > console .log ("cc")
            allSubseq ([c,c,c], "abc", 3)
            > console .log ("ccc")

These should help make it clear what's happening, and why you don't want to keep passing the fixed index + 1.

But I also want to point out a much simpler implementation:

const call = (fn, ...args) => 
  fn (...args)

const subseqs = ([c, ...cs]) => 
  c == undefined
    ? ['']
    : call ((ss = subseqs (cs)) => ss .flatMap (s => c + s) .concat (ss))

const allSubseq = (s) => 
  subseqs (s) .filter (Boolean) // remove empty string

console .log (allSubseq ('abcd'))
.as-console-wrapper {max-height: 100% !important; top: 0}

Here the main recursive function is subseqs. We wrap it in allSubseq to remove the empty string that is generated in subseqs. If you want to keep that empty string, then it's simpler still.

We use call as a way to define, calculate, then use and reuse the variable ss in a function body that contains only expressions and not statements. If this is confusing, we can skip the call and achieve the same thing with statements and a local variable like this:

const subseqs = ([c, ...cs]) => {
  if (c == undefined) return ['']
  const ss = subseqs (cs)
  return ss .flatMap (s => c + s) .concat (ss)
}

In either case, our base case is when the input string is empty, and we return an array containing only the empty string. If it's not, we calculate the subsequences for the tail of the string (everything but the first character) and return first those new subsequences prefixed by the first character and then those subsequences directly.

Note that this function does not print your results to the console, just returns them. This is clearly more flexible. If you want to print them individually, you can do something like console .log (allSubseq ('abcd') .join ('\n')) or allSubseq ('abcd') .forEach (console .log).

1 Please see How to debug small programs and What is a debugger and how can it help me diagnose problems?

2You can view the tweaked source code for i + 1 and index + 1

Scott Sauyet
  • 49,207
  • 4
  • 49
  • 103