Minimum Subset Sum Difference Explained | Tug Of War | Recursion and Backtracking in JAVA
ฝัง
- เผยแพร่เมื่อ 14 ต.ค. 2024
- 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 explain the Minimum Subset Sum Difference problem also known as Tug of War problem using recursion. In this problem,
1. You are given an array of n integers.
2. You have to divide these n integers into 2 subsets such that the difference of sum of two subsets is as minimum as possible.
3. If n is even, both set will contain exactly n/2 elements. If is odd, one set will contain (n-1)/2 and other set will contain (n+1)/2 elements.
3. If it is not possible to divide, then print "-1".
.....................................................................................................................................................................
Pepcoding has taken the initiative to provide counselling and learning resources to all curious, skilful and dedicated Indian coders. This video is part of the series to impart industry-level web development and programming skills in the community.
For better experience and well organised free resources visit -
We also provide professional courses with live classes and placement opportunities.
DSA Level 1 and Level 2
www.youtube.co...
Webinar on GATE Preparation
• Video
Here is a roadmap to our Free study content and know more about our resources here - www.pepcoding....
We are also available on the following social media platforms: -
Facebook(Meta) - / pepcoding
Instagram - / pepcoding
LinkedIn - / pepc. .
Pinterest - / _c. .
Twitter - / pepcoding
TH-cam (English Channel)- / @pepcodingprogrammingi...
Also take a look at our placement assistance - www.pepcoding....
HAPPY PROGRAMMING!
Pep it up.....
#recursion #backtracking #tug of war
you know what after watching striver and some other videos I have came to conclusion that he's the best teacher just not famous enugh
its called perfection ! Explaination was amazing.
well My senior(Sunny bhaiya) joined pepcoding as instructor last year .
agar aapko mza aya to kya aap google pe hmara ek review daal sakte hain
www.google.com/maps/place/PepCoding.com/@28.6993713,77.1360927,17z/data=!3m1!4b1!4m7!3m6!1s0x390d03d054d3e717:0x4fd0fdfc3f27ffaf!8m2!3d28.6993666!4d77.1382814!9m1!1b1
One of the best explanation to this problem... I literally understood everything. Gonna recommend my friends as well.
Thanks for sharing
@@Pepcoding Sir but why are you uploading all your paid courses for free of cost??? It will definately cause you heavy losses i guess
Zero dislikes shows the level of content you are providing sir !!
If you like our efforts, please upvote the comments written by the students about Pepcoding here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Falling in love with your teaching style
This type of explanation and content at free of cost , thank you sir
Hi. the explanation is very good. However I could not understand(from coding point of view) how different array lists are generated using the recursion. It will more good if we are able to explain this too.
I think time complexity should be 2^n because for each value we have 2 choice i.e :-- 1.include in subset 1 and not in subset 2.
2.include in subset 2 and not in subset 1.
Hence there will be 2^n functions calls hence time complexity is 2^n.
we can also avoid permutations here by making only one call at start
Yup, Agreed there is no need to generate permutations.
Can u provide the code for the same
Amazing explanation sir
sir set1.size()
you can also use
if you notice the euler the combinations you think will be missed are present on other branches , the avoided combinations are the ones that were not going to be useful anyways .
Great explanation Sir ! Well done !
Thankyou beta!
I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
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)
@@Pepcoding Done Sir , Also I recommended your channel and website to my friends and shared your page on instagram too !
shoudln't it be set/size()
Set.size()**
If we do this, then we are making a call even if we got the max size of set... As per your example then we are making a call when the size is 3... which is not needed ... that's why set.size
if you make it
try checking on leetcode sir, the -36,36 test case fails
why need to maintain two sum, sum2 alwasy be totalsum-sum1, so just calculate total sum once when calling
Sir recursion k bahut sare achche questions krne hain sir aap recursion axxxe se explain Krte ho... Sir aur axxe axxe questions post kro sir plz..
Abhi wo confidence ni Aa rha abhi tak jo playlist ki h usse intermediate questions ko krne m dikkat Aa rhi
Recursion k....
beta level1 aur level2 ki recursion karne ke baad recursion mei nahi fassoge.
@@Pepcoding sir can you tell me the level 2 and level 3 Questions will be uploaded or not ... Apart from level 1 only recursion and backtracking part is uploaded in level 2 and rest level 2 and level 3 is still empty on your site pepcoding....
@@deepakojha151 yes of-course. bass slow chal rha hai. Par lage hue hain
@@Pepcoding thanxx a alot sir for your love and support..... Bss aise hi aashirwad banaye rakhiye place hone. Pe aapko credit pakka...
will this work for negative element
Thank you so much sir❤❤
Explanation was cool. But bro please explain in English so that everyone could get benefited.
Sir agar min ya max function k andar do recursive function call ho rahe ho,to wo kis order se execute hote hai. for example min(find(n-2),find(n-1)).
I think find(n-2) will do the whole recursive operation till it reaches the base case and then will start comparing with function(n-1)
inner to outer
why permutation? it should be combination
sir level up k recursion and backtracking m kitne ques aayenge around?
Total 50. Abhi abhi 22nd dala hai
@@Pepcoding sir 2 shift me krdena ,please abhi k lie doosre topic pe jump krdo please :)
very nice
Time and space complexity's kra do sir please sir bahut ajeeb lagta hai question samgha me as jata Vai wo pta nhi rhta hai please sir aur eski time complexity o(2^n) hogi Kya kyoki her value ke pass 2 option hai so 2^n hoga
Hanji beta, jaldi resume krege content bnana
awesomeeee sir, solution of the problem is not enough but the excellent solution of problem is matter ,and sir you provide the excellent solution of any problem.thnk u soo much sir
Thankyou beta!
I am glad you liked it. It's all with the effort and hardwork from our brilliant mentors(Subhesh sir and all the other teacher of pepcoding). 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 )
this logic/code won't work for array having duplicate elements.
then what, any more logic we can apply?
it worked for me
Good explanation sir🙏
Thanks and welcome. I request you to help us get a webinar in your college.
@@Pepcoding sir ham amity mai hai. Yaha padhne likhne ka mohol nhi hai😂😂😂
@@rahulbhatia3075 LMAO😂😂😂
Can anyone send thier implementation in python. Mine is not working.
class Solution:
def solve(self,n,arr):
self.min = float("inf")
self.ans=""
self.backtrack(arr,[],[],0,0,0,n)
print(self.ans)
def backtrack(self,arr,arr1,arr2,i,sum1,sum2,n):
if i==n:
if abs(sum1-sum2) < self.min:
self.min = abs(sum1-sum2)
self.ans = '[' + ', '.join(map(str,arr1)) + "] [" + ', '.join(map(str,arr2)) + "]"
return
if len(arr1) < (n+1)//2:
arr1 += [arr[i]]
self.backtrack(arr,arr1,arr2,i+1,sum1+arr[i],sum2,n)
arr1.pop()
if len(arr2) < (n+1)//2:
arr2 += [arr[i]]
self.backtrack(arr,arr1,arr2,i+1,sum1,sum2+arr[i],n)
arr2.pop()
n = int(input())
arr=[]
for i in range(n):
arr.append(int(input()))
obj = Solution()
obj.solve(n,arr)