How to Code Combinations Using Recursion
Vložit
- čas přidán 2. 09. 2020
- In this video, we provide a deep dive into what combinations are and how to determine all combinations using recursion.
Table of Contents:
0:18 Learning Objectives
0:38 Combinatorics Overview
1:18 What is a Combination?
3:28 Diagramming Combinations Using a Tree
6:57 Javascript Implementation Using Recursion
20:04 Time & Space Complexity
21:39 Recap
Need a review on recursion? Check out our other videos:
* Introduction to recursion: bit.ly/intro-to-recursion
* Advanced recursion with Fibonacci & Arrays: bit.ly/advanced-recursion
* Permutations: bit.ly/youtube-permutations
To access hundreds of real coding challenges on algorithms, React, SQL, and more along with nearly one million solutions, visit coderbyte.com/.
Stay up to date with interview prep tips and hiring trends at / coderbyte
Let us know how we can improve our videos here: bit.ly/youtube-algos-feedback - Věda a technologie
Alvin I've been studying data structures and algorithms for the past 6 months on various platforms (Leetcode, Algoexpert, CZcams, Stackoverflow, etc etc), and you are by far the best instructor I've come across. Nobody else even comes close, and you have a real gift in being able to simplify these problems while making it extremely clear through visualization. Thank you so much for this content you are providing!
hey @mariomanx7 I have also been learning ds from different platfroms like algoexpert. It would be nice to have an accountable buddy learning dsa. It would be great if we connect and help each other. Thanks.
for real
oh god. I don't know why I have never found this channel before in top search result. Its a treasure trove. Thanks a lot, sir.
Right
I was searching high and low for this channel again. Your video on memoization more specifically your techniques for implementing it really solidified it for me. I thought I had bookmarked, subscribed, and liked the video so I was filled with dread when I looked through my playlists, and likes and couldn't find it. But then I stumbled upon this video and was like "Ah it's him!"
Racking my brain preping of an interview and could not for the life of me remember how to do combinations. This explained it so well, thank you! Thinking of the tree starting with the empty combination set and not the arr of numbers you want to combine is what clicked for me. Thank you so much!!
long live my Master. love your way of teaching. you should live forever to teach generations
Hey Alvin thanks for your well crafted videos, to be honest I was implementing it by myself at the beginning and I was doing quite well then I came across with the option of having the nested foreach and I got really hesitant and stop trusting myself. So I came here and this gave me hope ! thanks
This was so amazing and useful to learn. Thank you very much!
Ugh I had to watch this 4 times and draw several diagrams to finally get it. Thanks so much great video.
Wow! This is so clear and helpful! Thanks a million!
This guy is really gifted genius in both .. programming skills & teaching abilities..he made the most difficult part of programming quite simple. Thanks a alot 🙏🏼
The most lucid explanation by so far
Gold is not always buried underground. If found here on top of the floor. Thanks, Alvin to democratize quality education for everyone. Watching from somewhere in Africa.
Just got here after the Dynamic Programming one at FCC.
These are all great, good job!
Awesome. Thanks for watching. -Alvin
For anybody who's working in a synchronous language, no, you did not go insane. The recursive call to 'combinations' will always result in an empty array and the for loop below it will only ever get executed once... after the recursive call to 'combinations' completes.
Thanks for mentioning this. I am working with C# and this behavior did puzzle me.
Alvin explains problems perfectly and I am purchasing his Structy course tomorrow because he understands and explains problems way better than the rest.
However, this explanation had me a little confused because the visualization didn’t match the code implementation like he normally does.
The recursion was just a stack of 4 function calls with a loop on the inside of an array increasing by 2 for each nth call back up the stack. This gives the function a O(2^n) complexity.
The code that would match the visualization would require two recursive calls. You can think of each branch of the visualization like a recursion call.
I don’t understand how const combsWithoutFirst = combinations(rest); produces the output [ [ ], [ ‘c’ ], [ ‘b’ ], [ ‘c’, ‘b’ ] ]
Did you ever understand how this happened? If so can you explain it to me, please. I think I get everything else but I just don't know how we get [ b ] as rest when firstEl is "a"
This video is really helpful, a clear and thorough explanation. Thanks Coderbyte! I've been looking for a similar video which goes into detail on computing combinations while allowing individual elements to be repeated more than once. So, the Python itertools 'combination_with_replacement' function! Maybe an idea for your next video :)!
You were born to teach. Thank you.
Excellent presentation. Easy to understand. Thank You.
You are an excellent teacher. This is one of the best illustration I saw after mycodeschool's Harsha's. Thanks a lot for sharing it for FREE as well, this means a lot to all who wouldn't be able to afford otherwise.
In next video, please help dry run the program too. visualising and backtracking in recursive is complex to dry run :(
Thanks for the feedback. Glad to hear that you found it useful! When you say "help dry run the program", what are you referring to? -Alvin
@@CoderbyteDevelopers the code walkthrough with stackframe( how and where the return happens, how the final result is formed). Btw, for this problem, I finally after a couple of trials, i could finally see through. so it's ok for now, however it really gets too confusing when a recursive call is using the loop index like in the permutation program (like how and where return with what value and how all the results are joining back)
fantastic explaination, thanks Alvin.
You're a life savior
Thanks so much, you explained it very well and easy to understand
- Alvin you are the best, great explanation, was so easy to follow up the explanation with python and golang.
Really Amazing Tutorials
It amazing channel
Please keep going 🙏🏼🙏🏼
simply incredible.
Well done! thank you
Thank you, should have learnt this before my interview with Amazon
Now I know :)
Man, you explain things like God, thanks a lot
Very good! Thanks.😁
Thanks. Finding all combinations of a set is also called Power Set.
Hey Alvin!!! Thanks for your videos. You are the best, I mean it. All your videos are so beginner friendly and understandable. I have learnt a lot from those videos. Keep that up buddy!!!
Excellent presentation. Here is an implementation of the same in Haskell
allCombinations :: [a] -> [[a]]
allCombinations [] = [[]]
allCombinations (x:xs) = combinationsWithoutFirst ++ combinationsWithFirst
where
combinationsWithoutFirst = allCombinations(xs)
combinationsWithFirst = map ( \comb -> x : comb ) combinationsWithoutFirst
nice tutorial!
a very random question, i like how you explained a high-level concept before diving into implementation details!!
what equipments did you use for your video recording?
This is a wonderful lecture!!! Do you have any Github projects?
Hey, thank you soo soooo much! Very awesome explanation, espacilly those "trees" helped me understanding the solution.
But in my project, i only want to get the combinations with X amounts (for example, only return the combinations with 3 digits.) I know, i could just check for the length, but i think that isn't good for the performance. Any solutions? thanks!
Great people gets helighted lately like tesla after watching dp video on free code camp i get to know here is great content from great person 😍😍😍
I know these are combinations and order doesn't matter, but your code produces results in different order than was presented on diagram.
Hey Man, great video. I'm having trouble with a similar (but different) function and maybe you can help me out.
I need to create all possible combinations of options in different N groups, taking only one option from each group and having all groups represented in each combo result.
For example, one group might be "color" with options "black", "white" and "red", another group "size" with options "S", "M" and "L", and another group might be "material" or whatever.
This should return:
Black S, Black M, Black L, White S, White M, White L, Red S, Red M, Red L
All combinations should have one (and only one) option from each group and it should work for any amount of groups and options.
Thanks in advance!
Hello, this is unreal content, fair play. I've just implemented this into my code to see how it all works and stopped on various lines with the debugger. Upon using it, I just have one question: you have the empty array that you could have picked as an option all the way through as described by you. I've looked over it and at the end these repeated [] should be in every element in the array so I'm wondering where do these go. I had a suspicion that they were not being added in the push, but would I be right in saying that this code gets rid of them basically.
const test_array = [];
test_array.push([ ...[] , 'b'])
So because there are no contents inside in the empty array, using the spread operator pulls out nothing and thus it never gets added to the test_array (your arrangements_with_first ) just the second parameter, the 'b' in this case giving a result of this - test_array = ['b']
So the return array value from each of the recursive functions thus only has one [] empty array from the very start base case?
Would love to know if I'm right, thanks
hello Adams..wished I know very well to debug...but the [] was being spread in line 10(comes back as the first return and I believe this comes as a bubble) and when it is spread...more or less vanishes when it's picked from it array container in the loop cus it's empty...if only I did computer science 😭😭
How to can get repeating values also like 12,21
What if I say, combination of 4 characters of "a-z", e.g. "abcd", "axyb", etc? How can this work?
Hi Alvin, super amazing teaching technique! I have a question, how can we do this using tabulation? I tried a few attempts but to no avail. Also, I am also happy to donate to your channel if you provide a link.
Ok so I gave it a shot myself and came up with this:
function combinations(elements) {
const table = [];
const results = [];
for(let i=0; i
on line 9 there is nothing in combsWithoutFirst. how are you able to iterate through without having anything in there? :/
I'm somehow not able to implement this logic in python. Any help would be really appreciated
Thank you so much for the amazing videos! Your dynamic programming videos saved my life and I was so happy to find this one as well!
A quick question on time complexity. shouldn't it be O(n * 2^n)? because in each combinations, we spread (copy) arrays? Could you explain how these copy operations affect the time complexity?
- a) when we iterate through combsWIthoutFirst => const combWithFirst = [...comb, first]
- b) when we build return result => [...combsWithoutFirst, ...combsWithFirst]
Thank you!
Yes TC will be O(2^n*n) as in each operation we are going through the loop and also copying the values which will be O(n). and regarding your question for 1st part,the answer is copying operations is for n times (for rest of array and for 1st element) and they are taking place in forEach loop which runs for n time. in that loop the copying operation is taking place which will take in total O(n) for loop and + O(n) for copying so it is O(n) and for 2nd part the process of printing and going through all levels of recursion takes O(2^n*n) Tc in total .It hope this helps .If I am wrong then plz tell me!
This one does not handle duplicates right ? [ 1, 2, 2, 3] ?
Do anybody know how to handle the duplicates ?
Would u share the code in excel vba array?
I think the space complexity for the combination could be wrong, we return 2^n set that represent the combination of set of n, it is not correct that we say the space complexity is O(n^2) it should be count for the response size which is 2^n
I have the same question, but not sure what the answer is? The space complexity should be O(2^n)? Some of the stack frame will hold a lot more elements than n^2.
Thank you for the video! Not sure why my python solution doesn't work
def backtrack(nums):
if len(nums) == 0:
return [[]]
first_el = nums[0]
rest = nums[1:]
combinationWithoutFirst = backtrack(rest)
combinationWithFirst = []
print(combinationWithoutFirst)
for c in combinationWithoutFirst:
combination = list(c)
combination.append(first_el)
combinationWithFirst.append(combination)
return combinationWithoutFirst+combinationWithFirst
where have you been?
How we can make combinations without recursive call, because recursive call can take a lot of Memory if we give a large sell like an array of 100+ numbers
Alvin is so good! Go a/A
I dont think the time complexity is 2^n when you use javascript slice. You are technically removing and creating new array underneath with that method and that takes a great amount of time. Probably better off using pop than slice.
Also, will be great if you can include the optimal and clean solution for combination. The solution you shown might be easy to understand but might not be the fastest and cleanest when come to code challenge or interview. It might ran out of time when running test cases in LeetCode.
Instead of slice. Just elements.shift() to get the first element and you shorten the elements array at the same time.
Wouldn't you not want to mutate the original array? .shift() would mutate the original array, whereas .slice() simply makes a shallow copy of the array. I've heard it's usually bad practice to mutate your original input
Do you have a Java code for this? BTW thank you for this it really helps ♥
Glad you enjoyed the video! I'm no Java programmer, but I whipped up a quick translation of the solution in Java pastebin.com/NmrFU618 . Cheers. -Alvin
@@CoderbyteDevelopers thank you ♥
Hello Sir...
So I put a Scanner to the code you gave me then I thought it was doing alright until I realized I'm not hitting the base case if I input //input: []
// the output is :
[[,]]
[[],[[],[]],[],[]]
// and if I input a space or nothing it doesn't return anything when I'm using Scanner ...but in the code you gave me if I input space I got an output
//[]
[[]]
I've done many things already and still don't get the base case please help.
Thank so much ♥
btw this is my code...
package Recursion;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Scanner;
class Combination{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter an Array Elements: ");
String s = scan.next();
String str[] = s.split("");
ArrayList list = new ArrayList(Arrays.asList(str));// Create an ArrayList
System.out.println(list);
System.out.println(combinations(list));
}
public static ArrayList combinations(ArrayList list) {
if (list.size() == 0) {
ArrayList outer = new ArrayList();
ArrayList inner = new ArrayList();
outer.add(inner);
return outer;
}
else {
ArrayList result = new ArrayList();
String firstEl = list.get(0);
ArrayList rest = new ArrayList(list.subList(1, list.size()));
ArrayList withoutFirst = combinations(rest);
for (ArrayList comb : withoutFirst) {
result.add(comb);
ArrayList withFirst = (ArrayList) comb.clone();
withFirst.add(firstEl);
result.add(withFirst);
}
return result;
}}
}
Hey - `Scanner.next()` will keep reading input until the next complete token is typed and enter is pressed. A blank line is not accepted by `Scanner.next()`, however you could use `Scanner.nextLine()` instead to also accept blank lines as an empty array! Here's that code with that small change pastebin.com/FWaMRQUE .
@@CoderbyteDevelopers thank you so much for the help ♥ 😊
Genuine request - Could you please cook this one up in Python pls!
When abstracting away everything non-essential:
const reducer = (acc, cur) => [
...acc,
...acc.map(combs => [...combs, cur]),
]
const combinations = arr => arr.reduce(reducer, [[]])
Nice!
Guy: If you wanted to dealing with another language, all I'm doing here is just concatenating 2 arrays
Java: Yea, won't be that dossy ain't it mate?
Wait is it just me, or the code doesn't work? how does line 6 generate the combos?
Level 🤍
Anyone here from RIT Advance OOP classes? assignment 1.2?
Here is the simplified version of the above code :
const combinations = elements => {
if (elements.length === 0) return [ [ ] ]
const [first, ...rest] = elements
const combs = [ ]
combinations(rest).forEach(c => {
combs.push(c)
combs.push( [ first , ...c ] )
})
return combs
}
If you like FP style then this one is even simpler :
const combinations = elements => {
if (elements.length === 0) return [[]];
const [first, ...rest] = elements;
return combinations(rest).reduce((combs, c) => [...combs, c, [first, ...c]], [ ]);
};
This is not all options where is [a, c, b], [ b, c, a]??
Pretty sure it's O(n*2^n) time and space complexity. You generate 2^n combinations that are at most n characters in length and these are being stored for the result. Your algorithm has to generate each of those results at least once, which gives you O(n*2^n) time. The video completely ignores the cost of copying arrays. The explanation of the diagram and how to solve the problem was otherwise good. Just the analysis at the end is wrong.
Great content but plz, could you stop using the phrases "kind of" and "right?". Would make the delivery much better.