Question

write the code using c++ ( textbook from Date Structure using c++)

Write a function that generates the squares of the first N integers and then separates these squares into 2 sets so that difference between the sum of the squares in the first set and the the sum of the squares in the second set is a small as possible. The function's parameter is N. The function returns the two sets of squares and two sums of their squares.

Answer 1

#include <bits/stdc++.h>

using namespace std;

int findMinRec(int arr[], int i, int n, int sumCalculated, int sumTotal)

{

  if (i==0) {

    return abs((sumTotal-sumCalculated) - sumCalculated);

}

return min(findMinRec(arr, i-1, n, sumCalculated+arr[i-1], sumTotal),

      findMinRec(arr, i-1, n, sumCalculated, sumTotal));

}

int findMin(int n)

{

  int arr[n];

for (int i=1; i<=n; i++) {

arr[i-1] = i*i;

}

int sumTotal = 0;

  for (int i=0; i<n; i++)

    sumTotal += arr[i];

  return findMinRec(arr, n, n, 0, sumTotal);

}

int main()

{

  int n = 10;

  cout << "The minimum difference between two sets is " << findMin(n);

  return 0;

}