Tug Of War

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

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

Note -> Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.
Input Format 
A number n
n integers
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= n <= 20
1 <= arr[i] <= 100
Sample Input 
6
1
2
3
4
5
6
Sample Output 
[1, 3, 6] [2, 4, 5]


  • Editorial

    If n is even, we will divide the elements of array into two sets of equal size else we will divide them in (n + 1) / 2 and (n - 1) / 2 size sets.

    We will use recursion and backtracking to solve this problem.

    At levels we will place the elements of array. Each element will have two options, either to be a part of set1 or set2.

    We will increase the complexity of the code if we make two calls at each level. It can reduced by checking whether the size of the current set is less than (n + 1) / 2. If it is, then only include the current element in that set.

    For even, if n is equal to 6, then by calculating (n + 1) / 2, we get 3. If the number of elements in current set is less than 3, include the current element else do not. The maximum number of elements in set can be 3, therefore there is no point of including it, if there are already 3 elements present in the set.

    For odd, if n is equal to 7, then by calculating (n + 1) / 2, we get 4. If the number of elements in current set is less than 4, include the current element else do not. The maximum number of elements in set can be 4, therefore there is no point of including it, if there are already 4 elements present in the set.

    Signature -

    public static void solve(int[] arr, int vidx, ArrayList set1,

                                ArrayList set2, int soset1, int soset2)

    arr - the input array

    vidx - the current index

    set1 - arraylist that stores the content of set1

    set2 - arraylist that stores the content of set 2

    soset1 - sum of set 1

    soset 2 - sum of set 2

    Code - 

    static int mindiff = Integer.MAX_VALUE;
                                static String ans = "";
                                public static void solve(int[] arr, int vidx, ArrayList
     set1, ArrayList
     set2, int soset1, int soset2) {
                                    if (vidx == arr.length) {
                                	if (Math.abs(soset1 - soset2) < mindiff) {
                                		mindiff = Math.abs(soset1 - soset2);
                                		ans = set1 + " " + set2;
                                	}
                                	return;
                                    }
                                
                                    if (set1.size() < (arr.length + 1) / 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) {
                                	set2.add(arr[vidx]);
                                	solve(arr, vidx + 1, set1, set2, soset1, soset2 + arr[vidx]);
                                	set2.remove(set2.size() - 1);
                                    }
                                }

    java false

    Code Explained -

    Initially vidx will be zero, set1 and set2 empty, soset 1 and soset 2 zero.

    If the set1.size() < (arr.length + 1) / 2, we will make a call for the option1 and add the current element in set1.

    If the set2.size() < (arr.length + 1) / 2, we will make a call for the option2 and add the current element in set2.

    In pre - order, we will add the current element in Array List and in post order we will remove it.

    Base Case -

    If the vidx is equal to the length of the array, it means we have used all the element. We will find the absolute difference of soset1 and soset2 and if it less than the static mindiff variable, we will update the mindiff and static variable ans string.  We will return from the base case.

    In the main function we will print the ans string.

    Recursion Tree -

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name