Problem: Triplet Sum in Array

Given an array A[] of n numbers and another number x, determine whether or not there exist three elements in A[] whose sum is exactly x.

Expected time complexity is O(n^2).

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is n and x, n is the size of array.
The second line of each test case contains n integers representing array elements C[i].

Output:

Print 1 if there exist three elements in A whose sum is exactly x, else 0.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 200
1 ≤ A[i] ≤ 1000

Example:

Input:
2
6 13
1 4 45 6 10 8
5 10
1 2 4 3 6

Output:
1
1

The idea is using combinations in itertools module, but it’s a little bit tricky.
Here’s the way that works:

from itertools import combinations
if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n, x = map(int, raw_input().split())
        l = map(int, raw_input().split())
        for __ in combinations(l, 3):
            if sum(__) == x:
                print 1
                break
        else:
            print 0

but this does not work:

from itertools import combinations
if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n, x = map(int, raw_input().split())
        l = map(int, raw_input().split())
        for __ in list(combinations(l, 3)):
            if sum(__) == x:
                print 1
                break
        else:
            print 0

In the first one, we use generator expression, which in theory is more efficient in term of memory and speed. Because you don’t have to wait until the combinations function generate all combinations length 3 of the list, you simultaneously compute the combinations and check if that combination’s sum is exactly equal to x.
In the second one, you have to wait until the combinations function generate all the combinations length 3 of the list, which is unacceptable for this problem.

Advertisements