Minimum Subset Sum Difference Explained | Tug Of War | Recursion and Backtracking in JAVA

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 - nados.pepcoding.com/feed
We also provide professional courses with live classes and placement opportunities.
DSA Level 1 and Level 2
kzread.infop...
Webinar on GATE Preparation
• Video
Here is a roadmap to our Free study content and know more about our resources here - www.pepcoding.com/resources/
We are also available on the following social media platforms: -
Facebook(Meta) - / pepcoding
Instagram - / pepcoding
LinkedIn - / pepc. .
Pinterest - / _c. .
Twitter - / pepcoding
KZread (English Channel)- / @pepcodingprogrammingi...
Also take a look at our placement assistance - www.pepcoding.com/placements
HAPPY PROGRAMMING!
Pep it up.....
#recursion #backtracking #tug of war

Пікірлер: 57

  • @sainathpatil2820
    @sainathpatil28202 жыл бұрын

    This type of explanation and content at free of cost , thank you sir

  • @rakshitdevra7060
    @rakshitdevra7060 Жыл бұрын

    Falling in love with your teaching style

  • @ankurkumar8465
    @ankurkumar84653 жыл бұрын

    One of the best explanation to this problem... I literally understood everything. Gonna recommend my friends as well.

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    Thanks for sharing

  • @ankurkumar8465

    @ankurkumar8465

    3 жыл бұрын

    @@Pepcoding Sir but why are you uploading all your paid courses for free of cost??? It will definately cause you heavy losses i guess

  • @bunnyrabits
    @bunnyrabits3 жыл бұрын

    its called perfection ! Explaination was amazing. well My senior(Sunny bhaiya) joined pepcoding as instructor last year .

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    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

  • @darkpheonix6592
    @darkpheonix65924 күн бұрын

    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

  • @ashutoshtiwari4719
    @ashutoshtiwari47193 жыл бұрын

    Zero dislikes shows the level of content you are providing sir !!

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    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 )

  • @aryaraj1898
    @aryaraj1898 Жыл бұрын

    Thank you so much sir❤❤

  • @rakshitdevra7060
    @rakshitdevra7060 Жыл бұрын

    Amazing explanation sir

  • @aayushkumar9430
    @aayushkumar94302 жыл бұрын

    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.

  • @vishwashdwivedi9469
    @vishwashdwivedi94693 жыл бұрын

    Great explanation Sir ! Well done !

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    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)

  • @vishwashdwivedi9469

    @vishwashdwivedi9469

    3 жыл бұрын

    @@Pepcoding Done Sir , Also I recommended your channel and website to my friends and shared your page on instagram too !

  • @nishthagoyal5018
    @nishthagoyal50183 жыл бұрын

    very nice

  • @LegitGamer2345
    @LegitGamer23453 жыл бұрын

    we can also avoid permutations here by making only one call at start

  • @guptapaaras

    @guptapaaras

    3 жыл бұрын

    Yup, Agreed there is no need to generate permutations.

  • @vantal4115

    @vantal4115

    2 жыл бұрын

    Can u provide the code for the same

  • @rohandevaki4349
    @rohandevaki4349 Жыл бұрын

    try checking on leetcode sir, the -36,36 test case fails

  • @Ash-fo4qs
    @Ash-fo4qs2 жыл бұрын

    will this work for negative element

  • @dipesh1401
    @dipesh14012 жыл бұрын

    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.

  • @sharuk3545
    @sharuk35453 жыл бұрын

    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

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    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 )

  • @ananyaarya2465
    @ananyaarya24653 жыл бұрын

    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)).

  • @swapnildhiman6585

    @swapnildhiman6585

    2 жыл бұрын

    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)

  • @derilraju2106

    @derilraju2106

    2 жыл бұрын

    inner to outer

  • @amandixit3555
    @amandixit35553 жыл бұрын

    sir set1.size()

  • @sharuk3545

    @sharuk3545

    3 жыл бұрын

    you can also use

  • @curiouswatcher4626

    @curiouswatcher4626

    3 жыл бұрын

    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 .

  • @SBlogIndia
    @SBlogIndia2 жыл бұрын

    why need to maintain two sum, sum2 alwasy be totalsum-sum1, so just calculate total sum once when calling

  • @rishabs5991
    @rishabs59913 жыл бұрын

    shoudln't it be set/size()

  • @rishabs5991

    @rishabs5991

    3 жыл бұрын

    Set.size()**

  • @gulshansharma9377

    @gulshansharma9377

    2 жыл бұрын

    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

  • @aahanaganjewar9951

    @aahanaganjewar9951

    2 жыл бұрын

    if you make it

  • @rahulbhatia3075
    @rahulbhatia30753 жыл бұрын

    Good explanation sir🙏

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    Thanks and welcome. I request you to help us get a webinar in your college.

  • @rahulbhatia3075

    @rahulbhatia3075

    3 жыл бұрын

    @@Pepcoding sir ham amity mai hai. Yaha padhne likhne ka mohol nhi hai😂😂😂

  • @vishalkushwaha5373

    @vishalkushwaha5373

    3 жыл бұрын

    @@rahulbhatia3075 LMAO😂😂😂

  • @SCRIPTSAG
    @SCRIPTSAG3 жыл бұрын

    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

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    Hanji beta, jaldi resume krege content bnana

  • @prahladrana6391
    @prahladrana63913 жыл бұрын

    sir level up k recursion and backtracking m kitne ques aayenge around?

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    Total 50. Abhi abhi 22nd dala hai

  • @code7434

    @code7434

    3 жыл бұрын

    @@Pepcoding sir 2 shift me krdena ,please abhi k lie doosre topic pe jump krdo please :)

  • @TheSridharraj
    @TheSridharraj2 жыл бұрын

    Explanation was cool. But bro please explain in English so that everyone could get benefited.

  • @deepakojha151
    @deepakojha1513 жыл бұрын

    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....

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    beta level1 aur level2 ki recursion karne ke baad recursion mei nahi fassoge.

  • @deepakojha151

    @deepakojha151

    3 жыл бұрын

    @@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....

  • @Pepcoding

    @Pepcoding

    3 жыл бұрын

    @@deepakojha151 yes of-course. bass slow chal rha hai. Par lage hue hain

  • @deepakojha151

    @deepakojha151

    3 жыл бұрын

    @@Pepcoding thanxx a alot sir for your love and support..... Bss aise hi aashirwad banaye rakhiye place hone. Pe aapko credit pakka...

  • @deepakagrawal7687
    @deepakagrawal7687 Жыл бұрын

    why permutation? it should be combination

  • @arafatislam4648
    @arafatislam46483 жыл бұрын

    Can anyone send thier implementation in python. Mine is not working.

  • @derilraju2106

    @derilraju2106

    2 жыл бұрын

    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 = abs(sum1-sum2) self.ans = '[' + ', '.join(map(str,arr1)) + "] [" + ', '.join(map(str,arr2)) + "]" return if len(arr1) arr1 += [arr[i]] self.backtrack(arr,arr1,arr2,i+1,sum1+arr[i],sum2,n) arr1.pop() if len(arr2) 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)

  • @abhishekjaiswal6492
    @abhishekjaiswal64922 жыл бұрын

    this logic/code won't work for array having duplicate elements.

  • @dipeshsaili4468

    @dipeshsaili4468

    2 жыл бұрын

    then what, any more logic we can apply?

  • @learner5358

    @learner5358

    2 жыл бұрын

    it worked for me