Three Distinct Elements with a Target Sum

A valid group of three uses three distinct indices

For the array [3, 6, 4, 8, 1], a candidate is identified by three indices, not just by three values. If i, j, and k identify one group, require i < j < k. This means the positions are distinct, and it gives the group one fixed order. The values at those positions are then a[i], a[j], and a[k].

The condition i < j < k blocks two different mistakes. It prevents one position from being used twice, such as choosing index 1 for both i and j. It also prevents the same group from being counted again in another order, such as testing (3, 6, 8) after already testing (6, 3, 8). For this array, indices (0, 3, 4) represent the values 3, 8, and 1.

The bounds i < j < k generate every valid group exactly once

The first index must leave room for two later indices, so i runs from 0 through n - 3. Once i is chosen, j starts at i + 1 and ends at n - 2, because k still needs one position after it. Once j is chosen, k starts at j + 1 and ends at n - 1.

for (int i = 0; i <= n - 3; i++) {
    for (int j = i + 1; j <= n - 2; j++) {
        for (int k = j + 1; k <= n - 1; k++) {
            // test a[i], a[j], and a[k]
        }
    }
}

With n = 5, the loop visits candidates in this order: (0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), and then (0, 3, 4). After the last candidate with i = 0, the loops continue with i = 1 and produce (1, 2, 3), (1, 2, 4), and (1, 3, 4), followed by (2, 3, 4). No candidate repeats, and no valid group is skipped.

One matching sum is enough to answer true

For each candidate, calculate a[i] + a[j] + a[k] and compare the result with target, which is 12 here. The first five candidates have sums 13, 17, 10, 15, and 8. The sixth candidate is (0, 3, 4), and its values give 3 + 8 + 1 = 12.

if (a[i] + a[j] + a[k] == target) {
    return true;
}

Once one valid group has the target sum, the boolean result is already determined. There is no need to search for a second group, because the question asks whether at least one group exists. Returning true at (0, 3, 4) stops this run at candidate six instead of testing the four candidates that follow.

if (______________________________) {
    return true;
}

False belongs after all three loops, not inside them

A non-matching candidate proves only that one group does not work. The first candidate, (0, 1, 2), has sum 3 + 6 + 4 = 13, but other candidates may still match, and (0, 3, 4) does. Therefore, false must be returned only after every increasing index triple has been tested.

for (int i = 0; i <= n - 3; i++) {
    for (int j = i + 1; j <= n - 2; j++) {
        for (int k = j + 1; k <= n - 1; k++) {
            if (a[i] + a[j] + a[k] == target) {
                return true;
            }
        }
    }
}
return false;

For n = 5, there are ten possible groups of three indices: six beginning with index 0, three beginning with index 1, and one beginning with index 2. In general, the number of groups is n choose 3, which grows proportionally to n cubed. The direct three-loop method therefore has cubic worst-case work, because a run with no match may inspect every candidate. This particular run stops at its sixth candidate because it finds (0, 3, 4).