Concepts Used

Back Tracking

Difficulty Level

Hard

Problem Statement :

Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2. Print YES if it is possible to get the absolute minimum difference exactly 0, 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 is 8. 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 size 4 and sum of elements in both subsets is 4 and 4 respectively. (4-4=0).

Description:

We will use backtracking to solve the above problem by referring the best online learning sites for programming.
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 according to data structures and algorithms.
>
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 or (n-1)/2 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 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 in ith index is 1 we will say the element at ith index belongs to subset 1 else it belongs to subset 2.

Algorithm :

tow():

  1. if index==size, return
  2. recurvisely call tow() for next index.
  3. If index == size/2, store the absolute difference if it is less than the previous difference.
  4. include the current element in sum , sum = sum + a[index]
  5. assign subset 1 to the current index, (currElement[index] = true).
  6. recurvively call tow for next index.
  7. 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);

    }

}
Previous post Unique Power Set
Next post Find words

Leave a Reply

Your email address will not be published. Required fields are marked *