The twoSum problem is a standard coding challenge to find two numbers in an array that add up to a specific value.
In this Answer, we will learn how to solve the twoSum problem in Haskell.
Here's the formal problem statement:
Given an array of integers
Aand an integertarget, return all such pairs(x, y)from the array such thatx + y = target.
Let's start with our function declaration:
twoSum :: [Int] -> Int -> [(Int, Int)]
We declare the twoSum function, which takes two parameters:
A list of integers
An integer
The function returns a list of tuples of integer pairs.
Let's discuss the recursive case first:
Divide the list into three parts; the first element (x), the second element (y), and rest of the list (xs).
Check if the first (x) and second (y) elements add up to the target value. If yes, return a list containing this integer pair.
Otherwise, recursively call the twoSum function on the lists (x:xs) and (y:xs) until we reach the base case (discussed below) and join their results via the ++ operator.
The following code snippet shows the recursive case:
twoSum (x:y:xs) target| target == x + y = [(x, y)]| otherwise = twoSum (x:xs) target ++ twoSum (y:xs) target
We'll need two base cases to terminate the recursive call:
Empty list case: In case of an empty list, we return an empty list.
Singleton list case: If the list contains a single element, we return an empty list.
twoSum [] _ = []twoSum [_] _ = []
Note:
_token in Haskell represents a wildcard that matches any value.
Now that we have our recursive and base cases ready, let's test our implementation:
twoSum :: [Int] -> Int -> [(Int, Int)]twoSum [] _ = []twoSum [_] _ = []twoSum (x:y:xs) target| target == x + y = [(x, y)]| otherwise = twoSum (x:xs) target ++ twoSum (y:xs) target-- Main function to test the twoSum functionmain = doprint(twoSum [] 6) -- returns []print(twoSum [11] 11) -- returns []print(twoSum [2, 1, 3, 9] 5) -- returns [(2, 3)]print(twoSum [11, 3, 9, 5, 17] 20) -- returns [(11, 9), (3, 17)]
Lines 1–7: We define our twoSum function as stated above.
Lines 9–13: We define the main function and some test cases to test our twoSum function.
Free Resources