Triplets With A Given Sum In C Program

Finding three numbers in an array that sum up to a specific target value is a common problem in programming. This task involves iterating through combinations of numbers to identify those that meet the sum criteria. In this article, you will learn how to efficiently find triplets with a given sum using different C programming approaches.

Problem Statement

The core problem is to identify all unique (or distinct index-based) sets of three numbers (triplets) within a given array of integers whose sum equals a specified target value. This is a fundamental challenge in algorithm design, often appearing in interviews and competitive programming. For instance, given an array [1, 2, 3, 4, 5] and a target sum 6, we would look for combinations like (1, 2, 3).

Example

Consider the array nums = [12, 3, 4, 1, 6, 9] and the target sum 24.

A triplet that sums to 24 would be: [9, 12, 3]

Background & Knowledge Prerequisites

To understand the solutions presented, you should have a basic understanding of:

• C Programming Basics: Variables, data types, control flow (loops, conditionals).
• Arrays: Declaring, initializing, and accessing elements.
• Sorting Algorithms: Knowledge of how sorting works (e.g., qsort in C) will be beneficial for optimized approaches.

Relevant imports for this article will primarily include for input/output operations and for functions like qsort.

Use Cases or Case Studies

Identifying triplets with a specific sum has several practical applications:

• Financial Analysis: Finding three transactions that sum up to a specific audit flag amount.
• Game Development: In puzzle games, matching three items that combine to a target score or value.
• Data Analysis: Identifying patterns or outliers where three data points correlate to a certain threshold.
• Cryptocurrency Trading: Detecting three price movements or volumes that indicate a specific market trend.
• Resource Allocation: In manufacturing, combining three distinct resource types that meet a project's cost or material requirement.

Solution Approaches

We will explore two primary approaches to solve this problem: a straightforward brute-force method and a more optimized approach using sorting and the two-pointer technique.

Approach 1: Brute Force

This approach involves using three nested loops to check every possible combination of three distinct numbers in the array.

• Summary: Iterate through all unique combinations of three elements and check if their sum equals the target.
• Code Example:

// Triplet Sum - Brute Force
#include <stdio.h>

void findTripletsBruteForce(int arr[], int n, int targetSum) {
    printf("Triplets (Brute Force) for sum %d:\\n", targetSum);
    int found = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] == targetSum) {
                    printf("  (%d, %d, %d)\\n", arr[i], arr[j], arr[k]);
                    found = 1;
                }
            }
        }
    }
    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;

    findTripletsBruteForce(arr, n, targetSum);

    int arr2[] = {1, 2, 3, 4, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int targetSum2 = 10;
    findTripletsBruteForce(arr2, n2, targetSum2); // Example: 1+4+5, 2+3+5

    return 0;
}

Run

• Sample Output:

Triplets (Brute Force) for sum 24:
  (12, 3, 9)
  (12, 4, 6)
Triplets (Brute Force) for sum 10:
  (1, 4, 5)
  (2, 3, 5)

• Stepwise Explanation:

1. The outermost loop i selects the first element. It runs from the beginning of the array up to n-3 to ensure there are at least two elements remaining for j and k.
2. The second loop j selects the second element. It starts one position after i (i+1) to avoid duplicate combinations and ensure distinct elements. It runs up to n-2.
3. The innermost loop k selects the third element. It starts one position after j (j+1) for the same reasons. It runs up to n-1.
4. Inside the innermost loop, it checks if arr[i] + arr[j] + arr[k] equals targetSum. If true, the triplet is printed.
5. This method guarantees checking all unique combinations of three indices. Its time complexity is O(N^3).

Approach 2: Sorting + Two Pointers

This approach significantly improves performance by first sorting the array and then using a two-pointer technique.

• Summary: Sort the array. Iterate with one pointer (i) for the first element. For each arr[i], use two pointers (left and right) on the remaining array to find a pair that sums to targetSum - arr[i].
• Code Example:

// 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;
}

Run

• Sample Output:

Triplets (Sorting + Two Pointers) for sum 24:
  (3, 9, 12)
Triplets (Sorting + Two Pointers) for sum 9:
  (1, 2, 6)
  (1, 3, 5)
  (2, 3, 4)
Triplets (Sorting + Two Pointers) for sum 0:
  (-1, -1, 2)
  (-1, 0, 1)

• Stepwise Explanation:

1. Sort the Array: The first crucial step is to sort the input array. This enables the efficient two-pointer technique. qsort is used for this, requiring a comparison function.
2. Outer Loop (i): Iterate through the sorted array with a single pointer i from the start up to n-3. This arr[i] will be the first element of our potential triplet.
3. Handle Duplicates (Outer Loop): To avoid duplicate triplets (e.g., if the array has [1,1,2,3] and target 6, we don't want to find (1,2,3) twice if the 1s are identical), skip arr[i] if it's the same as the previous arr[i-1].
4. Initialize Two Pointers: For each arr[i], set a left pointer to i + 1 and a right pointer to n - 1. The goal is to find arr[left] + arr[right] that equals targetSum - arr[i].
5. Two-Pointer Loop: While left < right:
   • Calculate currentSum = arr[i] + arr[left] + arr[right].

1. The time complexity for this approach is O(N log N) for sorting and O(N^2) for the nested loops (N for the outer loop, and N for the two-pointer loop), resulting in an overall O(N^2) complexity, which is much better than O(N^3).

Conclusion

Finding triplets with a given sum in C can be approached in various ways. While the brute-force method is easy to understand, its cubic time complexity makes it inefficient for large datasets. The sorting and two-pointer technique offers a significant improvement, reducing the time complexity to quadratic, making it the preferred method for practical applications where performance is critical.

Summary

• The problem involves finding three numbers in an array that sum to a target value.
• Brute Force uses three nested loops, checking all combinations, with O(N^3) time complexity.
• The Sorting + Two Pointers approach is more efficient:
• Sort the array first (O(N log N)).
• Then, use an outer loop for the first element and two inner pointers (left and right) to find the remaining two elements (O(N^2)).
• Overall time complexity is O(N^2).
• Handles duplicate elements effectively to ensure unique triplets.
• Choosing the right algorithm significantly impacts performance, especially with large inputs.