C Program to find all pairs whose sum equals a given target

The pair-sum problem asks for two different array positions whose values add up to a given target. In this article, the program prints every matching index pair, not just the first one.

For example:

Array:  2 7 4 -1 5 3 8 0
Target: 7
Pairs:  (2, 5), (7, 0), (4, 3), (-1, 8)

Each array position is paired only with positions that come after it. This prevents the same two indices from being printed twice in reverse order.

C Program to Find All Pairs with a Given Sum

#include <stdio.h>

#define MAX_SIZE 100

int main(void) {
    int array[MAX_SIZE];
    int size;
    long long target;
    int pairCount = 0;

    printf("Enter the number of elements: ");
    if (scanf("%d", &size) != 1 || size < 1 || size > MAX_SIZE) {
        printf("Please enter a size between 1 and %d.\n", MAX_SIZE);
        return 1;
    }

    printf("Enter %d elements:\n", size);
    for (int index = 0; index < size; index++) {
        if (scanf("%d", &array[index]) != 1) {
            printf("Invalid array element.\n");
            return 1;
        }
    }

    printf("Enter the target sum: ");
    if (scanf("%lld", &target) != 1) {
        printf("Invalid target sum.\n");
        return 1;
    }

    for (int first = 0; first < size - 1; first++) {
        for (int second = first + 1; second < size; second++) {
            long long sum =
                (long long)array[first] + array[second];

            if (sum == target) {
                printf("Indices %d and %d: (%d, %d)\n",
                       first, second, array[first], array[second]);
                pairCount++;
            }
        }
    }

    if (pairCount == 0) {
        printf("No pair has the target sum.\n");
    } else {
        printf("Total matching pairs: %d\n", pairCount);
    }

    return 0;
}

Sample Output

Enter the number of elements: 8
Enter 8 elements:
2 7 4 -1 5 3 8 0
Enter the target sum: 7
Indices 0 and 4: (2, 5)
Indices 1 and 7: (7, 0)
Indices 2 and 5: (4, 3)
Indices 3 and 6: (-1, 8)
Total matching pairs: 4

How the Program Works

The outer loop chooses the first position of a pair. The inner loop examines every later position:

for (int first = 0; first < size - 1; first++) {
    for (int second = first + 1; second < size; second++) {
        if ((long long)array[first] + array[second] == target) {
            /* matching pair */
        }
    }
}

For each combination, the program adds the two values and compares the result with target. Matching pairs are printed immediately, and pairCount records how many were found.

Why Does the Inner Loop Start at first + 1?

Starting one position after first provides two guarantees:

1. An element is never paired with itself.
2. A pair is considered only once.

If indices 1 and 4 form a pair, the program checks (1, 4) but never checks (4, 1). Both represent the same index combination.

Starting the inner loop at 0 would also compare every element with itself and would print reversed duplicates.

Dry Run

For the array 2 7 4 -1 5 3 8 0 and target 7, the matching comparisons are:

First index	Second index	Calculation	Match?
0	4	2 + 5 = 7	Yes
1	7	7 + 0 = 7	Yes
2	5	4 + 3 = 7	Yes
3	6	-1 + 8 = 7	Yes

The loops also test every other index combination, but their sums do not equal the target and nothing is printed for them.

Index Pairs Versus Unique Value Pairs

The main program reports index pairs. If duplicate values occur at different indices, they represent different pairs.

Consider:

Array:  1 5 1 5
Target: 6

The matching index pairs are:

(0, 1), (0, 3), (1, 2), (2, 3)

All four pairs are valid because each uses a different combination of positions. Their value pair is (1, 5) each time.

If the requirement is to print each unique value pair only once, duplicate suppression must be added. One common approach is to sort a copy of the array, use two pointers, and skip repeated values after a match.

What If the Same Value Is Needed Twice?

Two different occurrences are required. For a target of 10:

Array:  5 5 8
Pair:   indices 0 and 1

A single 5 cannot be used twice because the loop never pairs an index with itself.

What If No Pair Exists?

When no sum matches the target, pairCount remains zero:

Array:  1 3 5
Target: 20
Output: No pair has the target sum.

The explicit message makes the result clear instead of producing an empty output.

Negative Numbers and Zero

No special handling is required. Addition and equality comparisons work for negative, positive, and zero values:

Array:  -5 0 2 7 10
Target: 5
Pairs:  (-5, 10), (0, 5) only if 5 is present, (2, 3) only if 3 is present

For the displayed array, only (-5, 10) is a matching pair.

Why Is the Sum Calculated as long long?

Adding two int values can overflow the int range before the result is compared with a wider target. The cast occurs before addition:

(long long)array[first] + array[second]

This converts the first operand to long long, so the entire addition uses the wider type. It also allows the user to enter a target outside the int range safely.

Does the Program Modify the Array?

No. The nested loops only read array values. The original order and contents remain unchanged, which is helpful if the array will be used again later.

Finding Unique Value Pairs with Sorting and Two Pointers

When only distinct value pairs are wanted, a sorted copy supports a more efficient scan:

1. Sort the copy in ascending order.
2. Place one pointer at the beginning and another at the end.
3. If their sum is too small, move the left pointer right.
4. If their sum is too large, move the right pointer left.
5. On a match, print the values and skip every duplicate of both values.

Sorting typically costs O(n log n), and the pointer scan costs O(n). A copy is necessary if the original order must remain unchanged.

Hash-Table Approach

A hash table can track values or indices already encountered. It can find matches in expected linear time, but printing all index pairs correctly requires storing every relevant prior index, especially when duplicates occur.

Standard C does not provide a built-in hash-table type. For a small beginner-level array, nested loops are straightforward, portable, and make the meaning of “all pairs” explicit.

How Many Comparisons Are Made?

For n elements, the number of different index pairs is:

n × (n - 1) / 2

For five elements, the loops check 5 × 4 / 2 = 10 combinations. This is much less than checking all n² ordered combinations, but it still grows quadratically.

Time and Space Complexity

For an array of n elements:

• Time complexity: O(n²) because every distinct pair of indices is examined.
• Extra space complexity: O(1) because the program uses only counters and a sum variable.
• Output size: Up to O(n²) index pairs can be printed when duplicate values create many matches.

When all pairs must be reported, the running time cannot be smaller than the amount of output in cases that contain quadratically many matching index pairs.

Common Mistakes

• Returning after the first match even though all pairs are required.
• Starting both loops at index 0 and printing reversed duplicates.
• Pairing an element with itself.
• Treating repeated value pairs as accidental duplicates when the requirement concerns index pairs.
• Forgetting to report that no pair exists.
• Allowing int addition to overflow before comparing it with the target.
• Sorting the original array even though its order must be preserved.

By making the second index start after the first, the program checks every valid pair exactly once and reports all index combinations whose values add up to the requested target.