C++ Exercises: Arrange the numbers of a given array in a way that the sum of some numbers equal the largest number in the array

Last update on December 20 2024 12:20:21 (UTC/GMT +8 hours)

Write a C++ program to arrange the numbers in a given array in a way that the sum of some numbers equals the largest number in the array.

Visual Presentation:

Sample Solution:

C++ Code :

#include <iostream> // Header file for input/output stream
#include <algorithm> // Header file for algorithms
#include <string> // Header file for string operations

using namespace std; // Using the standard namespace

// Function to determine if a subset of array elements sum up to the maximum number in the array
string array_addition_1(int* arr, const size_t array_size) {
  // If the array size is less than 2, return "False"
  if (array_size < 2)
    return "False";

  // Sort the array elements in ascending order
  sort(arr, arr + array_size);

  // Get the maximum number from the array
  const int max_number{ arr[array_size - 1] };

  // Check if the array contains negative numbers
  const bool negative_numbers{ arr[0] < 0 };

  do {
    int latest_sum{}; // Variable to store the running sum of array elements

    // Loop through the array elements to find subsets whose sum equals the maximum number
    for (size_t i{}; i < array_size - 1; i++) {
      latest_sum += arr[i]; // Add the current element to the running sum

      // If the running sum matches the maximum number, return "True"
      if (max_number == latest_sum)
        return "True";

      // If there are no negative numbers and the running sum exceeds the maximum number, break the loop
      if (!negative_numbers && latest_sum > max_number)
        break;
    }

  } while (next_permutation(arr, arr + array_size - 1)); // Generate permutations of the array

  return "False"; // Return "False" if no subset found with sum equal to the maximum number
}

int main() {
  // Declaration and initialization of arrays
  int nums1[] = {3, 5, 22, 10, 1, 3};
  cout << '\n' << array_addition_1(nums1, sizeof(nums1) / sizeof(nums1[0])); // Expected output: "true" 3 + 5 + 10 + 1 + 3 = 22
  int nums2[] = {4, 6, 15, 0, 1};
  cout << '\n' << array_addition_1(nums2, sizeof(nums2) / sizeof(nums2[0])); // Expected output: "false"
  int nums3[] = {2, 6, -1, 8, 1};
  cout << '\n' << array_addition_1(nums3, sizeof(nums3) / sizeof(nums3[0])); // Expected output: "true" 2 + 6 - 1 + 1 = 8 
  int nums4[] = {2, 2, 4, 6, 7};
  cout << '\n' << array_addition_1(nums4, sizeof(nums4) / sizeof(nums4[0])); // Expected output: "false"
  int nums5[] = {1, 1, 1, 1, 1, 0, 5};
  cout << '\n' << array_addition_1(nums5, sizeof(nums5) / sizeof(nums5[0])); // Expected output: "true" 1 + 1 + 1 + 1 + 1 = 5
  return 0; // Return 0 to indicate successful execution
}

Sample Output:

True
False
True
False
True

Flowchart:

C++ Code Editor:

Click to Open Editor

Contribute your code and comments through Disqus.

Previous: Write a C++ program to find the number of pairs of integers in a given array of integers whose sum is equal to a specified number.
Next: Write a C++ program to find the second lowest and highest numbers in a given array.