Redirecting to
NADOS


  Prev   Next

Tug Of War







Knowing trees, I understand the meaning of patience. Knowing grass, I can appreciate persistence.

Tug Of War

Welcome back coder to yet another question, "Tug of War". So be mindful while going through this article, it is quite an easy problem.
We want you to go through the problem link to understand the outline of this question.

Importan Link : Problem Link, Solution Video Link

  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 minimum.
  3. If n is even, both sets will contain exactly n/2 elements. If n is odd, one set will contain (n-1)/2 and the other set will contain (n+1)/2 elements.
  4. If it is not possible to divide, then print "-1".
    5. We understand this question by taking [a, b, c, d] as the input array.

RECURSION TREE

We first make a tree for solving the given array [a, b, c, d]. It is shown in Figure 1.

img

  1. In the above figure, we have written the elements in set1 on the left side and the elements in set 2 on the right side i.e. set1|set2.
  2. Initially, at the bottom most level, set 1 and set 2 both are empty.
  3. Now our first element 'a' has a choice to be in either set 1 or set2 which is depicted by the second level of the tree.
  4. Again, our next element 'b' has 2 options. Either it can be on the same side of 'a' or the other side.
  5. The next 2 levels denote the options that 'c' and 'd' elements have.
  6. Since we have used up all the elements of the array, we check which options are divided according to the question. We need the 2 sets to have either equal elements or at most a difference of one element between them.
  7. The desired options are highlighted with green.
  8. Out of these desired options, we select the one whose difference of sum of the two subsets is minimum.

CODE

Since we have seen how the working of this problem takes place, we will now move to coding it.

We want you to give it an honest try first. If you get stuck, don't worry. Just refer to the code given below.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } solve(arr, 0, new ArrayList<>(), new ArrayList<>(), 0, 0); System.out.println(ans); } static int mindiff = Integer.MAX_VALUE; //mindiff= minimum difference static String ans = ""; public static void solve(int[] arr, int vidx, ArrayList<Integer> set1, ArrayL ist<Integer> set2, int soset1,int soset2) { if(vidx==arr.length){ //1 int delta=Math.abs(soset1-soset2); if(delta<mindiff){ mindiff=delta; ans=set1+" "+set2; } return; } if(set1.size()<(arr.length+1)/2){ //2 set1.add(arr[vidx]); solve(arr,vidx+1,set1,set2,soset1+arr[vidx],soset2); set1.remove(set1.size()-1); } if(set2.size()<(arr.length+1)/2){ //3 set2.add(arr[vidx]); solve(arr,vidx+1,set1,set2,soset1,soset2+arr[vidx]); set2.remove(set2.size()-1); } } }
java; true";

Here, "vidx" = index of the array, soset1=sum of set 1 elements and soset2=sum of set 2 elements.

  1. BASE CASE: When we reach the end of the array and the choices for all the elements have been made, we need to find in which option the difference of sum of two subsets is minimum.
    For doing so, we take the absolute difference of the sum of set 1 and the sum of set This difference is compared with the "mindiff" so far.
  2. We check if the size of set1 is smaller than one more than half the size of the array (this handles the case for odd size as well as even size). If it is, then, we add the given element to the set1. Now we make a recursion call for the next element of the array. Reader, don't forget to add the current element to the soset1. While backtracking we remove the element that we had previously added from the set 1.
  3. The process mentioned in //2 is also executed for set 2.
TIME COMPLEXITY- O(n)
SPACE COMPLEXITY- O(n)

We conclude this problem here. If you have any doubts about the solution, we suggest you watch the solution video of this question.

We will see you in the next question.

Author: Shreeya Gupta
 
Run
Id Name