How to generate subsets of an array - Inside code
Vložit
- čas přidán 23. 04. 2021
- Source code: gist.github.com/syphh/085a9cd...
🔴 Learn graph theory algorithms: inscod.com/graphalgo
⚙ Learn dynamic programming: inscod.com/dp_course
💡 Learn to solve popular coding interview problems: inscod.com/50problems_course
⌛ Learn time and space complexity analysis: inscod.com/complexity_course
🔁 Learn recursion: inscod.com/recursion_course
NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent
I also post content on LinkedIn (inscod.com/linkedin) and Instagram (inscod.com/instagram) - Věda a technologie
This will definitely be useful some day after university. Thanks!
Tried all of these in Ruby. You could replace the string-conversion in the second approach with a few shifts and bit-ands.
Here is my list, sorted by speed (List was 20 elements long, ran each 25 times in jruby):
1. Your 3rd approach (300ms)
2. My version of the 3rd approach (Similar but with more explicit copying) (530ms)
3. 1st approach (recursive) (780ms)
4. 2nd approach without strings but shifts and & instead. (3100ms)
5. 2nd approach with strings. (6500ms)
Let this be a warning to all: Even if a solution looks smart, it might not be the best and if it looks horrible, it might not be too bad.
I wasted a lot of time understanding it, thanks to this amazing video I finally understood :).
You finally explained it the correct way. Take for example the classic CCI, where they say that subset can be generated with your method (3) and then they code up the method (1). Like, wth why? You are the only one (aside from neet code) that has the code matching up to the explanation. Many build a tree and then use code that clearly doesnt generate that tree.
Second solution is Classic. Thank you, Bro. Request to make algorithmic problems like this.
You're welcome! That's what I do, check other videos
-- full implementation of this function in Haskell:
powerset = filterM (const [False,True])
It filters all items in the input list by the predicate `const [True,False]`, which for each item basically says it should be _both_ included (True) and excluded (False). This therefore encompasses all possible subsets.
@@WilcoVerhoef wait is this the entire code?
As always, such a high quality video explaining the ideas very well. Thanks!
You're welcome!
This was very helpful ❤️
Amazing explanations, thank you.
2 nd solution is too good.. and this made me to have clear idea of subsets thank you
Really helpful. Thanks a lot
Always delivering quality content!
Sureee
keep up your work
My solution in Haskell is just 4 lines:
subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) =
subsets xs ++ map (x:) (subsets xs)
is haskell a programming language?
Never mind I learnt Haskell in these six months and I gotta say using the ++ would make it really slow here wouldn't it?
Or is it amortized efficiency over-all?
Pretty Good video, i really enjoy ur content
Thanks a lot!
This is a very good vide, thank you.
You are welcome!
Do javascript tips and tricks videos please ❤️❤️