A Mismatch Does Not End the Pair Search

One failed pair cannot rule out a later match

For the array [4, 2, 7, 1] and target value 8, the first candidate pair is 4 and 2. Their sum is 6, so this pair does not work. That result rejects only the indices holding 4 and 2 together. It says nothing about the other indices, which may still form a matching pair.

bool hasPairSum(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                return true;
            }
            return false;  // wrong: this runs after the first mismatch
        }
    }
    return false;
}

The early return makes the function stop after checking 4 + 2 = 6, so it reports false before reaching the later pair 7 + 1 = 8. A mismatch means only that the current candidate pair is invalid. The search must continue until it finds a match or has no legal pair left to check.

Starting j at i + 1 checks every valid pair exactly once

A pair must use two different indices. The single 4 at index 0 cannot be paired with itself at index 0, so the inner loop must begin at i + 1. This also prevents reversed duplicates: after checking indices 0 and 1, there is no need to check indices 1 and 0, because both checks use the same two array elements.

For [4, 2, 7, 1], the nested loops examine the six legal index pairs in this order: (0,1), (0,2), (0,3), (1,2), (1,3), and (2,3). Their sums are 6, 11, 5, 9, 3, and 8. The final pair, indices 2 and 3, reaches the target.

True belongs at the match, but false belongs after both loops

The decision structure has two different stopping rules. When arr[i] + arr[j] equals the target, return true immediately, because one valid pair is enough to prove the answer. When a candidate pair misses, do nothing except let the inner loop continue. A mismatch has not disproved the existence of another pair.

bool hasPairSum(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                return true;
            }
            return false;  // move this after both loops
        }
    }
}

For the running array, the checks for 4 + 2, 4 + 7, 4 + 1, 2 + 7, and 2 + 1 all miss target 8. The check at indices 2 and 3 produces 7 + 1 = 8, so return true belongs there. If that check also missed, return false would be justified only after the inner loop and the outer loop had both completed.

bool hasPairSum(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) return true;
            return false;
        }
    }
}

Finding 7 + 1 requires all six legal checks

The array has four elements. The first index can pair with three later indices, the second can pair with two later indices, and the third can pair with one later index. That gives 3 + 2 + 1 = 6 legal pairs. In the running example, the matching pair is last, so the search performs all six checks before returning true.

For an array of n elements, the number of distinct-index pairs checked by this loop is n * (n - 1) / 2. This grows proportionally to n squared, so the worst-case time complexity is O(n^2). The loop stores only its indices and a few temporary values, so its extra space complexity is O(1).