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
A
and 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