Problem of the Day
A new programming or logic puzzle every Mon-Fri

3 Sum Problem

Welcome back to Monday!

Given an array of integers can you find 3 integers that add to 0? For bonus points can you find all the unique combinations of 3 integers that add to 0? Here is a sample array:

[1, 5, -2, 3, -1, -2, 4, -6, 10, 7, -3]

Note: (-2, -2, 4) is valid but then (-2, 4, -2) would not be considered valid.

Permalink: http://problemotd.com/problem/3-sum-problem/

Comments:

  • David - 9 years, 9 months ago

    Turns out itertools makes this pretty smooth in Python.

    from itertools import combinations

default_list = [1, 5, -2, 3, -1, -2, 4, -6, 10, 7, -3]
for number_set in combinations(default_list, 3):
    if(sum(number_set) == 0):
        print number_set

    Nested for loops would be a way to do it and ensure unique combinations*, but that would be far more tedious. Perhaps I will do that if I come back with a C version of this problem.
    I leave it as an exercise to the reader (including my future self) to demonstrate that and/or a more efficient method in C.
    *Note: combinations are unique in the sense of array position use, not numerical use.

    reply permalink

Content curated by @MaxBurstein