This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)
Personal note: It’s been an extremely challenging couple of weeks for me, due to a family emergency. As such I’m combining my solutions into a single, shorter blog post this week. If you also follow my review posts on the perlweeklychallenge.org site, you’ll note they are quite late as well. I’m sorry about that! Hopefully things will settle down so I can get back into my rhythm!
Task 1 › 3Sum Problem
The 3Sum (or kSum) problem is another classic in computer science. With this, you are given a target sum ($T
) and a list of integers (@L
), and are asked to find all unique sets of 3 numbers in @L
that sum to $T
.
Perl
The brute force way is to simply have a 3-nested loop and try all combinations of integers in @L
, and build a list of the sets that sum to $T
. But we can eliminate the inner loop entirely if we pre-build a hash of all numbers greater than a given number: