{"id":2256,"date":"2020-06-15T01:37:06","date_gmt":"2020-06-15T01:37:06","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2256"},"modified":"2022-03-23T07:53:06","modified_gmt":"2022-03-23T07:53:06","slug":"tug-of-war","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/tug-of-war\/","title":{"rendered":"Tug of War"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Back Tracking<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a set of n<\/code> integers, divide the set in two subsets of n\/2<\/code> sizes each such that the difference of the sum of two subsets is as minimum as possible. If n<\/code> is even, then sizes of two subsets must be strictly n\/2<\/code> and if n<\/code> is odd, then size of one subset must be (n-1)\/2<\/code> and size of other subset must be (n+1)\/2<\/code>. Print YES if it is possible to get the absolute minimum difference exactly 0<\/code>, else print NO.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

Idea is to divide the whole set into two halves. We will try every possible subset to fill the first half of the set, once the half set is filled we can say the remaining elements belongs to the other half. We have to keep the absolute difference minimum possible (in our case its 0<\/code>).
\nFor example, given set, {20, 0, 19, 2 ,-20, -3, 4 ,-14}<\/strong>, the size of set is 8<\/code>. Output for this set should be "YES"<\/strong>. {19,2,-3,-14}<\/strong> and {20,0,-20,4}<\/strong> are the two sets formed. Both output subsets are of size 4<\/code> and sum of elements in both subsets is 4<\/code> and 4<\/code> respectively. (4-4=0)<\/code>.<\/p>\n<\/blockquote>\n

Description:<\/h4>\n
\n

We will use backtracking to solve the above problem.
\nBacktracking<\/strong> is the approach to solve the problem by testing all possible answers (by breaking the problems into subproblems). If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.<\/p>\n

As mentioned above we will divide the whole set into two and try every possible subset, once we make a subset with length n\/2<\/code> or (n-1)\/2<\/code> depending upon the size is even or odd, we stop and store the difference of both the subsets. Every element must either belong to the subset 1<\/strong> or subset 2<\/strong>. We continue doing this for every subset. Once we are done we’ll have the minimum possible absolute difference. Aditionally, we also keep track of the elements which are chosen for subset 1<\/strong> (remaining elements automatically falls into subset 2<\/strong>) using a curr _element[ ] array. If the value in array in ith<\/code> index is 1<\/code> we will say the element at ith<\/sup> index belongs to subset 1<\/strong> else it belongs to subset 2<\/strong>.<\/p>\n<\/blockquote>\n

Algorithm :<\/h3>\n

tow():<\/h4>\n
    \n
  1. if index==size<\/code>, return<\/li>\n
  2. recurvisely call tow()<\/code> for next index.<\/li>\n
  3. If index == size\/2<\/code>, store the absolute difference if it is less than the previous difference.<\/li>\n
  4. include the current element in sum , sum = sum + a[index]<\/code><\/li>\n
  5. assign subset 1<\/strong> to the current index, (currElement[index] = true)<\/code>.<\/li>\n
  6. recurvively call tow<\/code> for next index.<\/li>\n
  7. unassign the current index from subset 1<\/strong> (currElement[index] = false)<\/code>.<\/li>\n<\/ol>\n

    Complexity Analysis :<\/h3>\n
    \n

    We are making two recursive calls each time and for every new call again 2 recursive calls . So the time complexity<\/strong> would grow exponentially! Can you guess the time complexity?<\/p>\n<\/blockquote>\n

    Solutions:<\/h3>\n\t\t\t\t\t\t