Combination of Characters in String (All subsets of characters)

Find combination of all characters in string where characters can be repeated.

[serhiypidkuyko]

Hi Tushar,
Thank you for your video.
This task can be done without a recursion as well.
The main idea is as follows: the set of all the subsets of k characters can be divided in two subsets A and B, where the A is the set of all subsets of (k-1) characters and the B is the set of subsets obtained from the A by union with the k-th character.
For example: for 'abc' A={{}, {a}, {b}, {a, b}}, B={{c}, {a, c}, {b, c}, {a, b, c}}
Here is the code in python (for all subsets of the set):
#
def all_subsets(s):
result=[set()]
for x in s:
dod=[]
for y in result:
z=y.copy()
z.add(x)
dod.append(z)
result.extend(dod)

print(result)
return result

def test():
s={1, 2, 3, 4}
all_subsets(s)

s='abcdeab'
s=set(s)
all_subsets(s)

[everywhere]

Hello from Australia.
I would like to thank you so much for these video. You make recursion problem so much easier to understand.

[kyrgyzcha-it]

Super awesome explanation, thank you!

[alisalman]

Hi Tushar, great video and explanation.
One question is at the end of the algorithm part you mentioned the complexity of time and size as O(2)^2 and O^2, what O stands for?

[jinwenxu]

Awesome work! Could you tell me why the time complexity is O(2^n)? Thanks!

[mehreenkhan]

i am having a lot of issues with algorithms and logarithms, any thing you can suggest?

[sheetalshireen]

Thanks for this awesome explanation!!!

[ramanpreet]

Your videos are amazing. Thanks for your contribution.
We can also do this question using binary number conversion.
Just want to know what advantage we get using recursion here ? 1 can see and that is sorted output, other than that ?

[fardadhajirostami]

Hey great content as always. I just wanted to point out that I've seen several of your videos and for some reason whenever you're explaining your code the video and audio skip at random times and some of your explanations get cut out. I'm not sure if it's a problem with your screen recorder but just thought you should know

[alessandrocamillo]

What about the solution `combinationEasy`. Can you please comment a bit on that one? It seems, indeed, easier than the presented one. Thanks

[anandsinha]

Hi sir, Great video. I am also adding my code for the same ques.
private static void comb(String s, int index, int lengthOfString) {
if(index == lengthOfString)
return ;
for(int k = index+1; k <= s.length(); k++)
System.out.println(s.substring(index, k));
comb(s, index+1, lengthOfString);
}

[vaibskinikar]

Hi Tushar, great video as always! I had one question. Wouldn't the time complexity for this be O(n^n) for a really large input?

[DrRobrez]

I really like this algorithm and it's similar counterpart for permutations

[shubhamrane]

What about this case ABCA,

Here having a count array won't work

[babalehman]

Could we use dynamic programming to solve this problem. I am trying at my end after gaining some insight from your dp videos.
for e.g comb(abcd) = comb(abc), comb(abd).
right hand side of above recursion ends with comb(ab) in repetition.
Thanks..

[akumarbond]

In the combination call inside the loop shouldn't it be combination(input, count, i+1, output, len) as we should start the next recursion from where we left off initially.

[blr]

Hi, I have a question. IF the required combination length is k, then is the time complexity O(2^k) or O(2^n). Code modification: I stop at kth depth in the recursion tree.

[ShivangiSingh-wcgk]

Beautiful Solution, never thought of it.

[elmesiasyourpapi]

Is there any formule by calculate the number of subsets?? (with repitition of characteres)

[nilutpalborgohain]

Great Video Sir .
Could you please make a video on Range Minimum Query using Sparse Table .
Thanks.