C Program to find all triplets whose sum equals a given target
Learn how to find every triplet of array indices whose values add up to a target using three nested loops in C.
The triplet-sum problem asks for three different array positions whose values add up to a given target. This program reports every matching combination of indices, rather than stopping after the first match.
For example:
Array: 2 7 4 -1 5 3 8 0
Target: 10
The matching value triplets include (2, 5, 3), (2, 8, 0), (7, 4, -1), (7, 3, 0), and (-1, 3, 8).
C Program to Find All Triplets with a Given Sum
#include <stdio.h>
#define MAX_SIZE 100
int main(void) {
int array[MAX_SIZE];
int size;
long long target;
int tripletCount = 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 - 2; first++) {
for (int second = first + 1; second < size - 1; second++) {
for (int third = second + 1; third < size; third++) {
long long sum = (long long)array[first]
+ array[second]
+ array[third];
if (sum == target) {
printf("Indices %d, %d, and %d: (%d, %d, %d)\n",
first, second, third,
array[first], array[second], array[third]);
tripletCount++;
}
}
}
}
if (tripletCount == 0) {
printf("No triplet has the target sum.\n");
} else {
printf("Total matching triplets: %d\n", tripletCount);
}
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: 10
Indices 0, 4, and 5: (2, 5, 3)
Indices 0, 6, and 7: (2, 8, 0)
Indices 1, 2, and 3: (7, 4, -1)
Indices 1, 5, and 7: (7, 3, 0)
Indices 3, 5, and 6: (-1, 3, 8)
Total matching triplets: 5
How the Program Works
Three nested loops select three different positions:
for (int first = 0; first < size - 2; first++) {
for (int second = first + 1; second < size - 1; second++) {
for (int third = second + 1; third < size; third++) {
/* check this triplet */
}
}
}
The indices always satisfy:
first < second < third
The program adds the values at those positions, compares the sum with target, and prints the triplet when they match.
Why Do the Loops Start at Different Positions?
The second loop begins at first + 1, and the third loop begins at second + 1. This arrangement provides three guarantees:
- The same array position cannot be used twice.
- Every three-index combination is checked.
- The same indices are not printed again in another order.
For example, the combination of indices 0, 2, and 5 is tested once as (0, 2, 5). Permutations such as (2, 0, 5) and (5, 2, 0) are never considered separately.
Why Do the First Two Loops Stop Early?
The first index must leave room for two later positions, so it stops before size - 2. The second index must leave room for one later position, so it stops before size - 1.
If the last valid index is size - 1, the final possible triplet is:
(size - 3, size - 2, size - 1)
These bounds prevent invalid array access and unnecessary loop iterations.
Dry Run
For the sample array and target 10, the successful combinations are:
| First index | Second index | Third index | Calculation |
|---|---|---|---|
| 0 | 4 | 5 | 2 + 5 + 3 = 10 |
| 0 | 6 | 7 | 2 + 8 + 0 = 10 |
| 1 | 2 | 3 | 7 + 4 + (-1) = 10 |
| 1 | 5 | 7 | 7 + 3 + 0 = 10 |
| 3 | 5 | 6 | -1 + 3 + 8 = 10 |
Every other combination is also examined, but it is not printed because its sum differs from the target.
Index Triplets Versus Unique Value Triplets
The main program reports combinations of indices. When duplicate values occur at different positions, multiple index triplets may display the same values.
For example:
Array: 1 1 1 1
Target: 3
The valid index triplets are:
(0, 1, 2)
(0, 1, 3)
(0, 2, 3)
(1, 2, 3)
All four are valid because they use different position combinations, even though every value triplet is (1, 1, 1).
If only unique value triplets are required, the program must suppress repeated value combinations. Sorting a copy and skipping duplicate values is a common solution.
Can One Element Be Used More Than Once?
No. A triplet requires three different indices. If the target is 15, one occurrence of 5 cannot be reused three times.
Array: 5 2 8
Target: 15
The values 5, 2, and 8 do form a valid triplet. By contrast, an array containing only one 5 cannot produce (5, 5, 5) unless two additional 5 values exist at different indices.
What If the Array Has Fewer Than Three Elements?
No triplet can be formed. The loop bounds cause the search to perform zero iterations, and the program prints:
No triplet has the target sum.
This safely handles arrays of size one or two without a separate special case.
What If No Matching Triplet Exists?
The variable tripletCount remains zero, allowing the program to print an explicit result:
Array: 1 2 4 8
Target: 100
Output: No triplet has the target sum.
Negative Numbers and Zero
The same comparisons work for every int value. Negative numbers can offset positive numbers, and zero can participate normally:
Array: -4 0 3 7 10
Target: 6
Triplet: (-4, 0, 10)
No special parity or sign handling is required.
Why Is the Sum Calculated as long long?
Adding three int values can overflow before the result is compared with a wider target. The first value is converted before any addition:
(long long)array[first] + array[second] + array[third]
Once the first operand is long long, the remaining additions also use long long arithmetic. Casting only after adding the three integers would not prevent an earlier overflow.
Does the Program Change the Array?
No. It only reads elements and prints matches. The original order and values are preserved for later use.
Faster Method for Unique Value Triplets
When unique value triplets are needed, sorting and two pointers reduce the search time:
- Sort a copy of the array.
- Fix one value with an outer loop.
- Place a left pointer immediately after it and a right pointer at the end.
- Move the pointers according to whether the three-value sum is smaller or larger than the target.
- On a match, print the triplet and skip duplicate values.
Sorting costs approximately O(n log n), and the repeated two-pointer scans cost O(n²). The total time is therefore O(n²), with additional space if a copy is used to preserve the original array.
Hash-Set Approach
For each fixed first element, a hash set can solve a two-sum subproblem among the later elements. This also takes expected O(n²) time.
Correctly reporting all index triplets and handling duplicates requires storing sufficient occurrence information. Standard C has no built-in hash-set type, so the triple-loop solution is simpler and fully portable for small arrays.
How Many Triplets Are Checked?
The number of different combinations of three indices from n elements is:
n × (n - 1) × (n - 2) / 6
For five elements, the program checks 5 × 4 × 3 / 6 = 10 triplets. For ten elements, it checks 120.
Time and Space Complexity
For an array of n elements:
- Time complexity:
O(n³)because the program examines every combination of three indices. - Extra space complexity:
O(1)because it uses only loop indices, a counter, and a sum variable. - Output size: Up to
O(n³)triplets may be printed. For example, if all values are zero and the target is zero, every index combination matches.
When every matching index triplet must be reported, output alone can require cubic time in the worst case.
Common Mistakes
- Returning after the first match instead of reporting all triplets.
- Starting every loop at index
0and generating repeated permutations. - Reusing the same array index more than once.
- Confusing index triplets with unique value triplets when duplicates are present.
- Using incorrect loop bounds and reading beyond the array.
- Allowing the three-
intaddition to overflow before comparison. - Modifying or sorting the original array when its order must remain intact.
By maintaining first < second < third, the program checks each valid three-index combination exactly once and prints every triplet whose values add up to the requested target.