How to solve the twoSum problem in Haskell

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 integer target, return all such pairs (x, y) from the array such that x + y = target.

Solution

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.

Recursive case

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

Base case

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.

Implementation

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 function
main = do
print(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

HowDev By Educative. Copyright ©2025 Educative, Inc. All rights reserved