Partition into Subsets Dynamic Programming | Explanation and Code
Vložit
- čas přidán 6. 08. 2020
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the question Partition into Subsets where we are required to find the number of ways in which n elements can be divided into k subsets such that no subsets is empty. In this problem,
1. You are given a number n, representing the number of elements.
2. You are given a number k, representing the number of subsets.
3. You are required to print the number of ways in which these elements can be partitioned in k non-empty subsets.
E.g.
For n = 4 and k = 3 total ways is 6
12-3-4
1-23-4
13-2-4
14-2-3
1-24-3
1-2-34
To attempt and submit this question, click here: www.pepcoding.com/resources/o...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#dp #dynamicprogramming
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Last year at this i didn't even had the laptop. I managed to purchase one in septempber, at that time i had zero knowledge of programming and now i can solve problems on my own.This is all possible because of you.
Thanks a lot sir for providing this amazing content for free.🙂🙂🙂😊😊
well explained
For such videos I hope CZcams gives a love react . Like doesn't justify the love for your videos sir.
Thanks for liking the content, I request you could write about our channel on your facebook or linkedin? So that maximum students could get the best out of it.
@@Pepcoding surely sir. Thanks for your hard work. This content helps people who can't afford handsome fees but need to learn DSA.
I WILL SURELY SHARE IT. THABKS AGAIN
17: 05 dp[4][5]=4*1+6=10. Beside that as usual Awesome explanation sir🔥
you are too good
22:25 Even after explaining soo well you did it all again. This really shows how passionate you are! Thank you sir!
Sir aapse behtar shayad ye problem koi aur nahi samjha pata. Thank you, and get well soon.
Thank you. Bro, linkedin ya fb pe ek post daal do channel ki. Bacho ko pta chal jaega.
@@Pepcoding Sure sir mai apne sabhi juniors ko advice krunga ki wo aapko follow kre.
The best channel. The best explanation and variety.
Thank you. May I request you to write about us on linkedin?
@@Pepcoding I am following you on LinkedIn from my different account.
Sir your teaching skill is awesome...
Thank you Sir.
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Thank you sir,
Most welcome
thanks for these videos
This is good question. Had to think hard to visualise everything.
hatsoff sir.. you are a legend.
Hope you love the explanation, for better experience and well organised content sign up on nados.io and start learning.
I love Pepcoding!!
amazing : )
hats off to your dedication sir!
Hope you like the video but if you want to excel your coding career with better experience and well organised content.
visit - nados.pepcoding.com
Don't forget to follow us on Instagram instagram.com/pepcoding/
sir how will we get intution of getting 2d dp
Sir, I am a big fan of your explanation 🤘
GAWD level content ❤️
was waiting eagerly for your videos
I hope I did justice with this one. Was feeling very weak.
Hope you like it. If yes, I request you to write about our channel on your facebook or linkedin? So that maximum students could get the best out of it.
@@Pepcoding Tabhi sir bahut aacha samjhaya aapne. Jaise formula aapne derive kara usse kaafi aacha thought process develop hua
God bless him!
For more such content, do check out nados.pepcoding.com
just wow
Can someone in the audience or @Pepcoding explain why are we considering to split the problem in two ways - eg (1234 in 3 teams) - 123(k) and 123(k-1) specifically. How did we get down to this?
lets say 1234(3)
so 4 will ask '123'
1. hey '123' an you divide yourselves into 3 team? 123(3)
if you guys can then i will join any one of the team
2. hey '123' can you divide yourself into 2 team? 123(2)
if you guys can then i will make a seperate team.
these two can be the possible scenarios
why 4 will not ask '123' to divide in 1 team? 123(1)?
because if it says so
then it will receive 1 team from 123(1)+ 4 alone can form 1 team + but from where it will bring the another team?
which was the main question => 1234(3)
how to get intution either we have to use 1d dp array or 2d dp array? seems like long way to go. :(
Same my problem
use 1d array when u WANT duplicates or permutations, use 2d array when u WANT combinations and DONT want duplicates. if u want to know why then search this video title on yt :- "Coin Change Problems Analysis | Leetcode 322 v/s 518 Explained | Dynamic Programming In-Depth" by pepcoding
Very nice sir
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
sir ek hi dil hai , kitni baar jeetogey,
sir, if i get placed in good company, then definitely all credit will go to you.
bas ho jaye achi company mein placed, i daily do 4 question from your playlist , and watching it in order with full dedication and discipline,
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Did you get placed?
Janab(😅chaman datt) kisi ki bas ki ni ha Ki itna shandar material free da paye thank you sir
Glad you liked it:) Please visit nados.pepcoding.com for more curated content like this :)
respect++, ❤❤❤❤❤
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
take a bow !!!
Amazing explanation, thanks.
I understood the solution but how to get this thought process. What are the key points in the question which will push us to choose this approach. Why have we chosen this approach is not clear.
as he says in previous video, thought process come from practicing more and more questions.
sahab tu bahot mast kam karta he!!!😁 jokes apart you are a great teacher Sumeet sir.
Thanks a ton.
For better experience sign up on nados.io
Sir how can we able to drive the formula by their own? I am unable to think like you think.
2 tareeke hain
1. +1, + 2 ka maths revise karke permutations and combinations mei ache ho jaie.
2. 200 DP questions solve kar lijie.
@@Pepcoding sir kal tk mera yeh "DP" foundation wala khtam ho jayega to sir mujhe ab phle 200 ka count pura karna chaiye (leetcode+level up apka ) ya phir phle agey ka foundation complete krloon phir apka level 2 or leetcode se 200 ka count pura karoon !!
@@anubhavgupta4412 did you completed foundation or level up
@@mickyman753 foundation completed . ..level up chl raha hai
@@anubhavgupta4412 bhai can you share how do you revise level1 ,and abhi kitna confidence aya hai level1 krne ke baad
Sir could you please explain why is it not equivalent to nCk ie n!/k!(n-k)!
Sir one test case is failing with recursion
import java.io.*;
import java.util.*;
public class Main {
public static int part(int n,int k){
if(n < k || k == 0 || n == 0){
return 0;
} else if(n == k || k == 1){
return 1;
}
return part(n - 1 , k - 1) + part(n - 1 , k) * k;
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int k = scn.nextInt();
System.out.println(part(n,k));
}
}
Sir itna observational formula skill chaiye!
Bhai tumne level 1 complete kar lia h kya
Sir hame pata kaise chale ga ki kab double dimensional array use karna aur kab single dimensional array?
for any problem first think for its recursion and in recursion when two dimensions are being varied then in those case 2-d dp is applied and
if there is only single dimension being varied then 1 -d dp is applied....
Also by doing more and more practice u will know where to use 1-d and where to use 2-d dp
Ok Sir understood
sir isme Why samaj nhi aya ? ki y formula kyu lagaya ??
Sir mtlb jyada question krne se hi problem solving ability bdhegi
yes
sir iss vedio mei aur isse pichli vedio mei badhi confusion hogaya hai, can you please elaborate the previos two problems in a simple way
beta backtracking mei inki details hain. wo dekhne ke baad asaan lagega.
Bhai pnc mains k revise krle
for n=0 and k=0 dp[0][0] =1
this is because 0 person can be divided in 0 teams in 1 way.
true,, but sir's solution works fine becoz dp[0][0] only matters for dp[1][1] and for that sir already placed for 1 team dp[1][i]=1; that's why it does not give wrong ans but for 0 team and for 0 persons answer will be one ,,,,,,sumit sir also teaches this in many recursion videos;
Sir mujha dp ka que hard lg rha hai . Mai roj 2 que krt hu dp ka mind headache hona lgta hai itna soch nhi pata.
Koi nh beta, dp k questions tede hote h aur easily approach nh click krti but jaise jaise aap zda number of questions practice kroge to vo thinking process build hota jayega aur fr aap further nye questions khud se bna paoge.
Thank u sir jai hind jai bharat.
Got placed?
Sir, if you tell the memoization and then let us convert it to dp, or even dont do it, the concept will make much more sense, also the question does not give tle for even pure recursion.
sir in first explanation at 5 players and 4team we will get 10 as answer and not 11
yes you are right
It should be
0 0 0 0 0 0
0 1 1 1 1 1
0 0 1 3 7 15
0 0 0 1 6 25
0 0 0 0 1 10
a
w
e
s
o
m
e
cringe ke liye maaf karna
thank you so much