Example: Triplet Sum - Sorting + Two Pointers in C

// Triplet Sum - Sorting + Two Pointers
#include <stdio.h>
#include <stdlib.h> // Required for qsort

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void findTripletsTwoPointers(int arr[], int n, int targetSum) {
    // Step 1: Sort the array
    qsort(arr, n, sizeof(int), compare);

    printf("Triplets (Sorting + Two Pointers) for sum %d:\n", targetSum);
    int found = 0;

    // Step 2: Iterate through the array with 'i' as the first element
    for (int i = 0; i < n - 2; i++) {
        // Skip duplicate 'i' elements to avoid duplicate triplets
        if (i > 0 && arr[i] == arr[i - 1]) {
            continue;
        }

        // Step 3: Initialize two pointers for the remaining subarray
        int left = i + 1;
        int right = n - 1;
        int currentTarget = targetSum - arr[i]; // Target sum for the remaining two elements

        // Step 4: Use two-pointer technique
        while (left < right) {
            if (arr[left] + arr[right] == currentTarget) {
                printf("  (%d, %d, %d)\n", arr[i], arr[left], arr[right]);
                found = 1;

                // Skip duplicate 'left' elements
                while (left < right && arr[left] == arr[left + 1]) {
                    left++;
                }
                // Skip duplicate 'right' elements
                while (left < right && arr[right] == arr[right - 1]) {
                    right--;
                }
                left++;
                right--;
            } else if (arr[left] + arr[right] < currentTarget) {
                left++; // Sum is too small, need a larger 'left' element
            } else {
                right--; // Sum is too large, need a smaller 'right' element
            }
        }
    }
    if (!found) {
        printf("  No triplets found.\n");
    }
}

int main() {
    int arr[] = {12, 3, 4, 1, 6, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int targetSum = 24;

    findTripletsTwoPointers(arr, n, targetSum);

    int arr2[] = {1, 2, 3, 4, 5, 6}; // Example with multiple solutions
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int targetSum2 = 9;
    findTripletsTwoPointers(arr2, n2, targetSum2); // 1+2+6, 1+3+5, 2+3+4

    int arr3[] = {-1, 0, 1, 2, -1, -4}; // Example with negative numbers and duplicates
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int targetSum3 = 0;
    findTripletsTwoPointers(arr3, n3, targetSum3); // Expected: (-1, -1, 2), (-1, 0, 1)

    return 0;
}