NOTE : This is solution gives output of all possible subsets and not all possible substrings substrings like AACB, CB,CAA etc needs to generated by some other technique. For that watch tushar's sir this video ruclips.net/video/nYFd7VHKyWQ/видео.html
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 ?
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
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.
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..
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
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?
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.
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)
As for time and space complexity: 1.time complexity = (n_1+1)*(n_2+1)*...*(n_k+1) where n_i is the count of the i-th symbol for example, let the input string length is 3*n if this string has 3 symbols of multiplicity n, then the time complexity will be (n+1)^3=o(2^3n) not a O(2^3n) if this string has n symbols of multiplicity 3, then the time complexity will be 3^n=o(2^3n) not a O(2^3n) 2.space complexity - when you're using the recursion in your code then to the time complexity you must include the size of the stack as well The given problem can be reformatted as follows: for the given list of natural numbers build all the lesser or equal lists for example, for the list [2,1,1] we have 3*2*2=12 lesser or equal lists: [2, 1, 1], [1, 1, 1], [0, 1, 1], [0, 0, 1], [0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 0, 0], [1, 1, 0], [2, 0, 1], [2, 0, 0], [2, 1, 0] Here is the code in python: # def all_subsets_of_list(li): def helper(c,k): print(c) for i in range(k,len(c)): if c[i]>0: #d=c.copy() c[i]-=1 helper(c,i) c[i]+=1 else: return print('initial given ->',li) helper(li,0) def test(): li=[2,1,1] all_subsets_of_list(li) li=[2,2,2,2] all_subsets_of_list(li) li=[4,4] all_subsets_of_list(li) li=[1,1,1,1,1,1,1,1] all_subsets_of_list(li)
Here is the code in python which is not using the recursion. # def all_subsets_of_list_iterative(li): print('iterative ->',li) stack=[] a=li.copy() stack.append((a,0)) while stack: a,h=stack.pop(0) print(a) for i in range(len(a)): if a[i]>0 and i>=h: b=a.copy() b[i]-=1 stack.append((b,i)) def test(): li=[2,1,1] all_subsets_of_list_iterative(li) li=[2,2,2,2] all_subsets_of_list_iterative(li) li=[4,4] all_subsets_of_list_iterative(li) li=[1,1,1,1,1,1,1,1] all_subsets_of_list_iterative(li)
That would be permutations. Where order does matter. This is combinations, where order doesn't matter, so any ordering differences are counted as duplicates. I would continue asking around though, I'm not 100% sure on this.
Hello ,can you help out .I'm trying to generate n! combinations of a 2d array ,such that every element is from different row and column .Like for a 3*3 array total combinations are 6
Hello from Australia.
I would like to thank you so much for these video. You make recursion problem so much easier to understand.
NOTE : This is solution gives output of all possible subsets and not all possible substrings
substrings like AACB, CB,CAA etc needs to generated by some other technique. For that watch tushar's sir this video ruclips.net/video/nYFd7VHKyWQ/видео.html
i am having a lot of issues with algorithms and logarithms, any thing you can suggest?
What about this case ABCA,
Here having a count array won't work
Awesome work! Could you tell me why the time complexity is O(2^n)? Thanks!
Because either we take the character or not, binary
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 ?
12 ppl from the other channels have disliked this video
Super awesome explanation, thank you!
What about the solution `combinationEasy`. Can you please comment a bit on that one? It seems, indeed, easier than the presented one. Thanks
Thanks for this awesome explanation!!!
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
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.
explanation is great, but code a little bit difficult
Great Video Sir .
Could you please make a video on Range Minimum Query using Sparse Table .
Thanks.
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..
Is there any formule by calculate the number of subsets?? (with repitition of characteres)
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
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?
O means the worst case complexity
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.
No. It would be nCk (pronounced n choose k) = n! / (k! × (n-k)!)
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)
As for time and space complexity:
1.time complexity = (n_1+1)*(n_2+1)*...*(n_k+1) where n_i is the count of the i-th symbol
for example, let the input string length is 3*n
if this string has 3 symbols of multiplicity n, then the time complexity will be (n+1)^3=o(2^3n) not a O(2^3n)
if this string has n symbols of multiplicity 3, then the time complexity will be 3^n=o(2^3n) not a O(2^3n)
2.space complexity - when you're using the recursion in your code then to the time complexity you must include the size of the stack as well
The given problem can be reformatted as follows:
for the given list of natural numbers build all the lesser or equal lists
for example, for the list [2,1,1] we have 3*2*2=12 lesser or equal lists:
[2, 1, 1], [1, 1, 1], [0, 1, 1], [0, 0, 1], [0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 0, 0], [1, 1, 0], [2, 0, 1], [2, 0, 0], [2, 1, 0]
Here is the code in python:
#
def all_subsets_of_list(li):
def helper(c,k):
print(c)
for i in range(k,len(c)):
if c[i]>0:
#d=c.copy()
c[i]-=1
helper(c,i)
c[i]+=1
else:
return
print('initial given ->',li)
helper(li,0)
def test():
li=[2,1,1]
all_subsets_of_list(li)
li=[2,2,2,2]
all_subsets_of_list(li)
li=[4,4]
all_subsets_of_list(li)
li=[1,1,1,1,1,1,1,1]
all_subsets_of_list(li)
Here is the code in python which is not using the recursion.
#
def all_subsets_of_list_iterative(li):
print('iterative ->',li)
stack=[]
a=li.copy()
stack.append((a,0))
while stack:
a,h=stack.pop(0)
print(a)
for i in range(len(a)):
if a[i]>0 and i>=h:
b=a.copy()
b[i]-=1
stack.append((b,i))
def test():
li=[2,1,1]
all_subsets_of_list_iterative(li)
li=[2,2,2,2]
all_subsets_of_list_iterative(li)
li=[4,4]
all_subsets_of_list_iterative(li)
li=[1,1,1,1,1,1,1,1]
all_subsets_of_list_iterative(li)
sir u r amazing
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?
No. Because for every character there are 2 possibilities. To be included or not to be included. So 2×2×... n times=2^n
I really like this algorithm and it's similar counterpart for permutations
cool..
what about aacb
you didnt explain this one
ya. i think the index logic has some bug to capture the scenario you rightly mention
similarly i would say 'aba'
That would be permutations. Where order does matter. This is combinations, where order doesn't matter, so any ordering differences are counted as duplicates.
I would continue asking around though, I'm not 100% sure on this.
Hello ,can you help out .I'm trying to generate n! combinations of a 2d array ,such that every element is from different row and column .Like for a 3*3 array total combinations are 6
Beautiful Solution, never thought of it.
why is it 211?
The count of each letter. There is two A, one B, and one C.