Find Triplets With Given Sum in Java
Problem
A triplet with a given sum is any three elements in the array whose values add up to a specific target number.
Given an array of integers and a target sum, find a triplet of elements that add up to the target.
Java Program
public class TripletWithSum {
public static void main(String[] args) {
int[] arr = {12, 3, 7, 1, 9, 5};
int target = 21;
outer:
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) { // only pair with later elements
for (int k = j + 1; k < arr.length; k++) { // only pair with elements later still
if (arr[i] + arr[j] + arr[k] == target) {
System.out.println("Triplet: (" + arr[i] + ", " + arr[j] + ", " + arr[k] + ")");
break outer; // exits all three loops at once
}
}
}
}
}
}Output
Core Logic
Trying every possible combination of three elements, and stopping as soon as one adds up to the target, checks every triplet directly.
- 1Three nested loops pick indices
i,j, andk, each starting just after the previous one, so the same triplet is never checked more than once. - 2
arr[i] + arr[j] + arr[k] == targetchecks whether the current triplet sums to the target. - 3The first matching triplet found is printed, and a labeled
breakexits all three loops immediately. - 4Because the loops scan the array in its original order, the triplet reported reflects whichever valid combination appears first that way — not necessarily sorted.
[12, 3, 7, 1, 9, 5] with target = 21, the combination at indices for 7, 9, and 5 is the first one found that sums to 21.Key Point: A labeled loop — outer: before the first for, and break outer; inside — is what lets a single break exit all three nested loops at once, instead of only the innermost one.
Why: Every combination of three indices is checked directly, so the triple-nested loop does up to n³ comparisons with no extra memory.
Key Concepts
Approach 2: Sort + Two-Pointer
import java.util.Arrays;
public class TripletWithSumTwoPointer {
public static void main(String[] args) {
int[] arr = {12, 3, 7, 1, 9, 5};
int target = 21;
Arrays.sort(arr);
outer:
for (int i = 0; i < arr.length - 2; i++) {
int left = i + 1;
int right = arr.length - 1;
while (left < right) {
int sum = arr[i] + arr[left] + arr[right];
if (sum == target) {
System.out.println("Triplet: (" + arr[i] + ", " + arr[left] + ", " + arr[right] + ")");
break outer;
} else if (sum < target) {
left++; // sum too small, grow it
} else {
right--; // sum too large, shrink it
}
}
}
}
}
Output
Core Logic
Sorting the array first, then fixing one element and using two pointers to search the rest, finds a matching triplet in far fewer comparisons than checking every combination.
- 1
Arrays.sort(arr)puts the array into ascending order first. - 2The outer loop fixes one element,
arr[i], as the smallest of the triplet being tested. - 3
leftandrightpointers start just afteriand at the end of the array, closing inward. - 4If the three-way sum is too small,
leftmoves inward to increase it; if too large,rightmoves inward to decrease it; a match prints the triplet immediately.
[12, 3, 7, 1, 9, 5] gives [1, 3, 5, 7, 9, 12]; fixing arr[i] = 5 and closing the pointers inward finds 5 + 7 + 9 = 21.Key Point: Sorting changes the order elements are visited in, so this can report the same triplet's values in a different order than the brute-force scan of the original array — both are correct, just different traversal orders over the same combinations.
Why: Sorting costs O(n log n), and the two-pointer scan runs at most n times for each of the n choices of the fixed element, so the nested cost is O(n²) — with Arrays.sort() needing O(n) auxiliary space for typical Java sorting implementations.