Tug Of War
1. You are given an array of n integers.Input Format
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.
A number nOutput Format
n integers
Check the sample ouput and question video.Question Video
1 <= n <= 20Sample Input
1 <= arr[i] <= 100
6Sample Output
1
2
3
4
5
6
[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