CSES Solutions - Apple Division

There are N apples with known weights given as arr[]. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Examples:

Input: N = 5, arr[] = {3, 2, 7, 4, 1}
Output: 1
Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8). Difference = 9 - 8 = 1

Input: N = 4, arr[] = {1, 2, 3, 4}
Output: 0
Explanation: Group 1 has weights 1 and 4 (total weight 5), and group 2 has weights 2 and 3 (total weight 5). Difference = 5 - 5 = 0

Approach: To solve the problem, follow the below idea:

The problem can be solved using Recursion by generating all the possible divisions. This can be done by making two choices at every index: either choose the element at the current index in the first group or not choose the element at the current index in the first group (choose the element in the second group). After traversing though the entire array, we can return the absolute difference of sum of elements between both groups.

Step-by-step algorithm:

• Maintain a recursive function solve(idx, arr,r sum1, sum2, N) which returns the minimum difference of weights between two groups if we are currently at index idx.
• Check if we have traversed the entire array, that is idx == N, then simply return the difference between the sum of weights of both the groups.
• Otherwise, explore both the cases when the element at index idx is chosen in the first group and when the element at index idx is chosen in the second group.
• After exploring all the possibilities, return the minimum possible weight difference between both the groups.

Below is the implementation of the algorithm:

#include <bits/stdc++.h> #define ll long long int using namespace std; ll solve(int idx, ll* arr, ll sum1, ll sum2, ll N) {  // If we have reached the end, return the difference  // between the sums  if (idx == N) {  return abs(sum1 - sum2);  }  // Choose the current apple in group 1  ll choose  = solve(idx + 1, arr, sum1 + arr[idx], sum2, N);  // Choose the current apple in group 2  ll notChoose  = solve(idx + 1, arr, sum1, sum2 + arr[idx], N);  // Return the minimum of both the choices  return min(choose, notChoose); } int main() {  // Sample Input  ll N = 5;  ll arr[] = { 3, 2, 7, 4, 1 };  // Call the recursive function to find the minimum  // difference between both the groups  ll ans = solve(0, arr, 0, 0, N);  cout << ans; } 

public class MinimumDifference {  static long solve(int idx, long[] arr, long sum1, long sum2, int N) {  // If we have reached the end, return the difference between the sums  if (idx == N) {  return Math.abs(sum1 - sum2);  }  // Choose the current apple in group 1  long choose = solve(idx + 1, arr, sum1 + arr[idx], sum2, N);  // Choose the current apple in group 2  long notChoose = solve(idx + 1, arr, sum1, sum2 + arr[idx], N);  // Return the minimum of both the choices  return Math.min(choose, notChoose);  }  public static void main(String[] args) {  // Sample Input  int N = 5;  long[] arr = { 3, 2, 7, 4, 1 };  // Call the recursive function to find the minimum difference between both the groups  long ans = solve(0, arr, 0, 0, N);  System.out.println(ans);  } } // This code is contributed by shivamgupta310570 

using System; class Program {  // Function to solve for the minimum difference  static long Solve(int idx, long[] arr, long sum1, long sum2, int N)  {  // If we have reached the end, return the difference  // between the sums  if (idx == N)  {  return Math.Abs(sum1 - sum2);  }  // Choose the current item in group 1  long choose = Solve(idx + 1, arr, sum1 + arr[idx], sum2, N);  // Choose the current item in group 2  long notChoose = Solve(idx + 1, arr, sum1, sum2 + arr[idx], N);  // Return the minimum of both choices  return Math.Min(choose, notChoose);  }  static void Main(string[] args)  {  // Sample Input  int N = 5;  long[] arr = { 3, 2, 7, 4, 1 };  // Call the recursive function to find the minimum  // difference between both groups  long ans = Solve(0, arr, 0, 0, N);  Console.WriteLine(ans);  } } 

function GFG(idx, arr, sum1, sum2, N) {  // If we have reached the end and   // return the absolute difference between the sums  if (idx === N) {  return Math.abs(sum1 - sum2);  }  // Choose the current apple in the group 1 and 2  const choose = GFG(idx + 1, arr, sum1 + arr[idx], sum2, N);  const notChoose = GFG(idx + 1, arr, sum1, sum2 + arr[idx], N);  // Return the minimum of both the choices  return Math.min(choose, notChoose); } // Main function function main() {  const N = 5;  const arr = [3, 2, 7, 4, 1];  // Call the recursive function to find the minimum   // difference between both the groups  const ans = GFG(0, arr, 0, 0, N);  console.log(ans); } main(); 

def solve(idx, arr, sum1, sum2, N): # If we have reached the end, return the difference # between the sums if idx == N: return abs(sum1 - sum2) # Choose the current apple in group 1 choose = solve(idx + 1, arr, sum1 + arr[idx], sum2, N) # Choose the current apple in group 2 not_choose = solve(idx + 1, arr, sum1, sum2 + arr[idx], N) # Return the minimum of both the choices return min(choose, not_choose) # Sample Input N = 5 arr = [3, 2, 7, 4, 1] # Call the recursive function to find the minimum # difference between both the groups ans = solve(0, arr, 0, 0, N) print(ans) 

1

Time Complexity: O(2 ^ N), where N is the number of apples.
Auxiliary Space: O(2 ^ N)