Problem: Find all four sum numbers

*Difficulty: Medium

Given an array A of size N, find all combination of four elements in the array whose sum is equal to a given value K. For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and K = 23, one of the quadruple is “3 5 7 8” (3 + 5 + 7 + 8 = 23).

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines. The first line of input contains two integers N and K. Then in the next line are N space separated values of the array.

Output:
For each test case in a new line print all the quadruples present in the array separated by space which sums up to value of K. Each quadruple is unique which are separated by a delimeter “$” and are in increasing order.

Constraints:
1<=T<=100
1<=N<=100
-1000<=K<=1000
-100<=A[]<=100

Example:
Input:

2
5 3
0 0 2 1 1
7 23
10 2 3 4 5 7 8
Output:
0 0 1 2 $
2 3 8 10 $2 4 7 10 $3 5 7 8 $

Approach:
Using itertools in Python, I can easily quickly generate all combination-length-four of an arr.

#code
from __future__ import print_function
import itertools

def allFourSumNumber(arr, K):
    result = []
    for four in itertools.combinations(arr, 4):
        if sum(four) == K:
            if four not in result:
                result.append(four)
    return result

def main():
    t = input()
    for _ in range(t):
        n, K = map(int, raw_input().strip().split())
        arr = map(int, raw_input().strip().split())
        found = False
        for four in allFourSumNumber(sorted(arr), K):
            found = True
            print(four[0], four[1], four[2], four[3], '$', end='')
        print(-1 if not found else '')

if __name__ == '__main__':
    main()

“Life is short, why haven’t you learned Python yet?”

Advertisements