Can you please also explain the complexity for this solution?
Get subsequences
@biradaraishwarya9,
Let’s say the string is abcd.
Now the result of this will be a + subsequences(bcd).
Answer of bcd will be b + subsequences(cd).
Answer of cd will be c + subsequences(d).
Answer of subsequences(d) will be d + subsequences(""), this is where we hit our base case and return arraylist with “” (empty string).
Now the for loop will be executed 1 time for empty string arraylist [""]. 2 times for arraylist ["",d]. 4 times for arraylist ["",d,c,cd]. 8 times for ["",d,c,cd,b,bd,bc,bcd].
The answer will be 1 + 2 + 4 + 8 = 15 = 2^4 - 1
Incase the string length is n. The answer will be 2^n - 1.
Hence O(2^n).
1 Like