I feel that the explanation of the solution in this video has been oversimplified in the sense that there is no logical explanation as to why recursion has been used.
Please explain logically in detail that why did we arrive at the conclusion that we need to use recursion and how recursion alone will solve this problem.
hello @shshwt.khr
the question is saying that we need to print maximum length of string generated by the concatenated of string in a subsequence of the array right?
so first we need to generated the subsequence of array.
do u know how we can do that ?
yeah, a subsequence of an array is any set of elements of that array that can be obtained by deleting some elements(possibly none) from that array. So, to generate the subsequence of an array, we need to find all possible combinations of the array elements(O(2^n complexity) I guess).
yes u r right it will be 2^n.
and there is method using recursion to generate all subsequence . we r just using the same.
method of generating subsequnce is described here->link
let me know if u still have any doubt
can we not optimize it to a better complexity?
we can add some small optimisation but it will not have much impact on time complexity.
the optimisation is ->
remove all those strings that have repeated character and then apply above stated method on remaining array
is there an iterative solution for this? if there is we can at least optimize the space complexity, right?
yes we can find the subsequence using bitmasking technique iteratively. that will be bit optimised.
can you give a link to its code?
So, there is a trade-off between time and space complexities in the iterative and recursive solutions respectively.
Iterative solution: O(n*2^n) time and O(1) space
Recursive solution: O(2^n) time and O(n) space
Right?
yeah space compilexity will be high in recursive case.
time complexity will be same .
no, time complexity is not same. they are different. that’s why there is a trade-off as I said.
generating susbet is always 2^n(be it recursive or iterative) and fi u furthure do any thing with the subset then it will be n * 2^n .
it(time complexity) is written on the same links you posted for each solution
yeah, so the time complexity are different(O(2^n) for recursive and O(n*2^n) for iterative), right?
no bro it is n * 2^n becuase they are printing susbet which is n for each subset. and becuase total susbets are 2^n . the total time will be n *2^n.
only differnt between iterative and recursive is space complexity
so, the time complexities written on the respective pages at the links you posted are wrong?
the n is actually l on the post.
this l is the length of the binary string
yeah the recursivve code has time compleiy n * 2^n.