Last Updated on March 23, 2022 by Ria Pathak
Concepts Used
Back Tracking
Difficulty Level
Hard
Problem Statement :
Given a set of
nintegers, divide the set in two subsets ofn/2sizes each such that the difference of the sum of two subsets is as minimum as possible. Ifnis even, then sizes of two subsets must be strictlyn/2and ifnis odd, then size of one subset must be(n-1)/2and size of other subset must be(n+1)/2. Print YES if it is possible to get the absolute minimum difference exactly0, else print NO.
See original problem statement here
Solution Approach :
Introduction :
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).
For example, given set, {20, 0, 19, 2 ,-20, -3, 4 ,-14}, the size of set is8. Output for this set should be "YES". {19,2,-3,-14} and {20,0,-20,4} are the two sets formed. Both output subsets are of size4and sum of elements in both subsets is4and4respectively.(4-4=0).
Description:
We will use backtracking to solve the above problem.
Backtracking 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.As mentioned above we will divide the whole set into two and try every possible subset, once we make a subset with length
n/2or(n-1)/2depending 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 or subset 2. 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 (remaining elements automatically falls into subset 2) using a curr _element[ ] array. If the value in array inithindex is1we will say the element at ith index belongs to subset 1 else it belongs to subset 2.
Algorithm :
tow():
- if
index==size, return - recurvisely call
tow()for next index. - If
index == size/2, store the absolute difference if it is less than the previous difference. - include the current element in sum ,
sum = sum + a[index] - assign subset 1 to the current index,
(currElement[index] = true). - recurvively call
towfor next index. - unassign the current index from subset 1
(currElement[index] = false).
Complexity Analysis :
We are making two recursive calls each time and for every new call again 2 recursive calls . So the time complexity would grow exponentially! Can you guess the time complexity?
Solutions:
#include <stdio.h>
#include<stdlib.h>
#define INT_MAX 999999
void TOWUtil(int* arr, int n, int* curr_elements, int no_of_selected_elements,
int* soln, int* min_diff, int sum, int curr_sum, int curr_position)
{
if (curr_position == n)
return;
if ((n/2 - no_of_selected_elements) > (n - curr_position))
return;
TOWUtil(arr, n, curr_elements, no_of_selected_elements,
soln, min_diff, sum, curr_sum, curr_position+1);
no_of_selected_elements++;
curr_sum = curr_sum + arr[curr_position];
curr_elements[curr_position] = 1;
if (no_of_selected_elements == n/2)
{
if (abs(sum/2 - curr_sum) < *min_diff)
{
*min_diff = abs(sum/2 - curr_sum);
for (int i = 0; i<n; i++)
soln[i] = curr_elements[i];
}
}
else
{
TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln,
min_diff, sum, curr_sum, curr_position+1);
}
// removes current element before returning to the caller of this function
curr_elements[curr_position] = 0;
}
// main function that generate an arr
void tugOfWar(int *arr, int n)
{
int* curr_elements = (int *)malloc(sizeof(int)*n);
// The inclusion/exclusion array for final solution
int* soln = (int *)malloc(sizeof(int)*n);
int min_diff = INT_MAX;
int sum = 0;
for (int i=0; i<n; i++)
{
sum += arr[i];
curr_elements[i] = soln[i] = 0;
}
TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0);
int sum1=0;
for (int i=0; i<n; i++)
{
if (soln[i] == 1)
sum1 += arr[i];
}
int sum2 = 0;
for (int i=0; i<n; i++)
{
if (soln[i] == 0)
sum2 +=arr[i];
}
if(sum1-sum2==0)
printf("%s\n","YES");
else
printf("%s\n","NO");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
tugOfWar(arr, n);
}
return 0;
}
#include <bits/stdc++.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
void TugofWarRecur(int* array, int n, bool* current_elements, int selected_elements_count,bool* solution, int* min_diff, int sum, int current_sum, int current_position)
{
if (current_position == n)
{
return;
}
if ((n/2 - selected_elements_count) > (n - current_position))
{
return;
}
TugofWarRecur(array, n, current_elements, selected_elements_count,solution, min_diff, sum, current_sum, current_position+1);
selected_elements_count++;
current_sum = current_sum + array[current_position];
current_elements[current_position] = true;
if (selected_elements_count == n/2)
{
if (abs(sum/2 - current_sum) < *min_diff)
{
*min_diff = abs(sum/2 - current_sum);
for (int i = 0; i<n; i++)
{
solution[i] = current_elements[i];
}
}
}
else
{
TugofWarRecur(array, n, current_elements, selected_elements_count, solution, min_diff, sum, current_sum, current_position+1);
}
current_elements[current_position] = false;
}
void TugOfWar(int *array, int n)
{
bool* current_elements = new bool[n];
bool* solution = new bool[n];
int min_diff = INT_MAX;
int sum = 0;
for (int i=0; i<n; i++)
{
sum =sum + array[i];
current_elements[i] = solution[i] = false;
}
TugofWarRecur(array, n, current_elements, 0, solution, &min_diff, sum, 0, 0);
int sumAdd=0;
for (int i=0; i<n; i++)
{
if(solution[i] == true)
{
sumAdd += array[i];
}
}
int sumAdd1=0;
for (int i=0; i<n; i++)
{
if(solution[i] == false)
{
sumAdd1 += array[i];
}
}
if(abs(sumAdd-sumAdd1) ==0)
cout<<"YES"<<"\n";
else
cout<<"NO"<<"\n";
}
//Main function
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
TugOfWar(arr,n);
}
return 0;
}
import java.util.Scanner;
public class Main {
static boolean []cur_ele;
static boolean []sol;
static int min_diff=Integer.MAX_VALUE;
public static void main(String[] args) {
// write your code here
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
int n =sc.nextInt();
int []arr = new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
TugOfWar(arr,n);
int sum1=0;
for(int i=0;i<n;i++)
{
if(sol[i]==true)
sum1+=arr[i];
}
int sum2=0;
for(int i=0;i<n;i++)
{
if(sol[i]==false)
sum2+=arr[i];
}
if(Math.abs(sum1-sum2)==0)
System.out.println("YES");
else
System.out.println("NO");
}
}
static void TugOfWar(int arr[] , int n)
{
cur_ele = new boolean[n];
sol = new boolean[n];
min_diff=Integer.MAX_VALUE;
int sum=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
cur_ele[i]=sol[i]=false;
}
TugOfWarRecur(arr,n,0,sum,0,0);
}
static void TugOfWarRecur(int arr[], int n, int selected, int sum, int curr_sum, int curr_pos )
{
if(curr_pos==n)
return;
selected++;
curr_sum=curr_sum+arr[curr_pos];
cur_ele[curr_pos]=true;
if(selected==n/2)
{
if(Math.abs(sum/2-curr_sum)<min_diff)
{
min_diff = Math.abs(sum/2-curr_sum);
for(int i=0;i<n;i++)
sol[i]=cur_ele[i];
}
}
TugOfWarRecur(arr,n,selected,sum,curr_sum,curr_pos+1);
selected--;
curr_sum=curr_sum-arr[curr_pos];
cur_ele[curr_pos]=false;
TugOfWarRecur(arr,n,selected,sum,curr_sum,curr_pos+1);
}
}
[forminator_quiz id="2258"]
This article tried to discuss the concept of Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on Backtracking you can check out MYCODE | Competitive Programming.