Maximum number of pairs with equal sum in an array

Updated

Given an array w of size n, consisting of non-negative integers, the task is to find the maximum number of pairs that can be formed, such that the sum of each of these pairs is equal.

Following are the constraints for pair formation:

  1. Each element of the given array can be a part of not more than a single pair.
  2. An element can’t pair up with itself.
  3. The pairs are unordered.
  4. It is not necessary to pair up all the elements of the array.

You are required to output the maximum number of pairs as well as the corresponding sum. If two or more sums are found corresponding to the maximum number of pairs, output the smaller one.

Examples :

Input : n=3, w={1, 3, 3}
Output : pairs: 1, sum: 4
Explanation :
Sets of pairs having equal sum are:
{1,3} - sum 4
{3,3} - sum 6.
No more than 1 pair can be formed for this test case, thus maximum
number of pairs is 1.

Input : n=6, w={1, 1, 3, 4, 2, 2}
Output : pairs: 2, sum: 3
Explanation :
Sets of pairs having equal sum are:
{1, 2}, {1, 2} - sum 3
{3, 2}, {4, 1} - sum 5
No more than 2 pairs having equal sum can be formed for this test
case, thus maximum number of pairs is 2.

Approach :

The sum of a pair that can be obtained from the array can neither be less than 2 times the minimum element of the array nor greater than 2 times the largest element, thus we find maximum number of pairs that can be obtained for each of the sums lying between these extremities and output the maximum amongst these along with it corresponding sum.

The approach for implementing this is as follows:

  1. Find the minimum and maximum elements in the array so as to obtain the bounds of the possible sum.
  2. Running the loop for sums ranging from 2* (minimum) to 2*(maximum) find the maximum number of pairs that can be formed having each of these sums.
  3. For finding such pairs as in step 2:
    1. Run nested loops, the outer one selects the first element of the pair and the inner one looks up the element giving the required sum with this element thus giving us the second element of the pair.
    2. Once a pair has been found the elements involved in this pair can’t be used again, to ensure that the code abides by this, maintain a vector to keep track of the indices of elements that are already a part of a pair.
    3. While making a new pair, only consider elements at indices that are absent from the vector of used elements.
  4. Keep track of the sum corresponding to the maximum number of pairs found yet and update it each time the number of pairs found with equal sums increases over this value.
  5. The maximum one amongst the numbers obtained in every run of the loop in step 2 will be the maximum number of pairs that can be formed possessing equal sum.
The array 1 2 3 4 5 where the pairs 1 and 4 and 2 and 3 both add up to 5 and the 5 is left out.

Implementation :

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 5, maxi = -1, w[n], M = 50, m = 1, max_sum = -1;

    for (int i = 0; i < n; i++)
        w[i] = i + 1;
    // w={1, 2, 3, 4, 5}

    // loop for finding number of pairs giving each possible
    // sum from min to max
    for (int i = 2 * m; i <= 2 * M; i++) {
        // since elements of w can't exceed M or be less
        // than m, the loop runs from minimum to maximum sum
        // possible

        vector<int> used;
        // the array elements already paired up can't be
        // reused, this vector keeps track of such elements

        int maxip = 0, curr_sum = i;
        // maxip holds number of pairs with sum i

        // loop for pairing up elements with sum i
        for (int j = 0; j < n; j++) {

            if (find(used.begin(), used.end(), j)
                == used.end())
                for (int k = 0; k < n; k++) {

                    if (k != j && w[j] + w[k] == i
                        && find(used.begin(), used.end(), k)
                               == used.end()) {

                        used.push_back(k);
                        used.push_back(j);
                        maxip++;
                        break;
                    }
                }
        }
        if (maxi < maxip)
            max_sum = curr_sum;
        maxi = max(maxi, maxip);
        // maxi holds the maximum number of pairs formed
        // amongst pairs with all considered sums yet
    }
    cout << "pairs: " << maxi << ", sum: " << max_sum;
}
Output

pairs: 2, sum: 5

Time Complexity : O((M-m)*2*n^2)

Auxiliary Space : O(n)

Comment
Next tutorial
Mithlesh Upadhyay Published 20 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials