Python Program To Check Triplet Sum

Count the number of unique triplets in an array that sum to a given target value S.

Understand the Problem

Problem Statement

Given N integers and a target sum S, find the count of unique triplets (combinations of three integers) from the array that add up to S.

The triplets are considered unique based on their values, not their positions in the array. For example, if the array contains duplicate values, they can form the same triplet value-wise but are counted as one occurrence.

Constraints

1 ≤ N ≤ 25
-10^5 ≤ S ≤ 10^5
-10^5 ≤ Each array element ≤ 10^5

Examples

Example 1

Input

4
10 20 50 20
50

Output

Explanation

The only unique triplet that sums to 50 is (10, 20, 20). Even though there are two 20s in the array, this forms only one unique combination.

Example 2

Input

7
3 9 -10 7 -12 -2 -5
0

Output

Explanation

The three unique triplets that sum to 0 are: (3, 9, -12), (7, -2, -5), and (3, 7, -10). All other combinations either don't sum to 0 or are duplicates of these.

Solution

#include <stdio.h>
#include <stdlib.h>

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

int countTriplets(int arr[], int n, int target) {
    qsort(arr, n, sizeof(int), compare);
    int count = 0;
    
    for (int i = 0; i < n - 2; i++) {
        // Skip duplicate elements for the first position
        if (i > 0 && arr[i] == arr[i-1]) continue;
        
        int left = i + 1;
        int right = n - 1;
        
        while (left < right) {
            int sum = arr[i] + arr[left] + arr[right];
            
            if (sum == target) {
                count++;
                
                // Skip duplicates for the second element
                while (left < right && arr[left] == arr[left + 1]) left++;
                // Skip duplicates for the third element
                while (left < right && arr[right] == arr[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    int target;
    scanf("%d", &target);
    
    printf("%d\n", countTriplets(arr, n, target));
    
    return 0;
}

Time:O(N²)

Space:O(1)

Approach:

Algorithm Steps:

Sorting: Uses qsort to sort the array in ascending order.
Three-pointer approach: For each element at index i, uses two pointers (left, right) to find pairs in the subarray [i+1, n-1].
Sum comparison: If sum equals target, increments count and moves both pointers past duplicates.
Optimization: If sum is less than target, moves left pointer forward; if greater, moves right pointer backward.
Duplicate handling: Skips duplicate values to count only unique triplets.

Time Complexity: O(N²) due to nested loops with two-pointer technique.

Space Complexity: O(1) as we only use a few extra variables.

Visual Explanation

Loading diagram...

All Problems