Abigail and Madeline, the instructor's daughters, are identical twins who love dancing, singing, drawing, knitting, and even felting. The girls are always making up stories, crafting things, or playing with their Pokemon. When it comes to math, however, the twins are not quite so fond of playing around with numbers 1...

For the past few days, Abigail and Madeline have been working on the triplet problem:

Given a list of numbers with n integers, determine if there are elements a, b, c, in numbers such that a + b + c = 0.  Find all unique triplets in the list of numbers.

For example, given the following numbers:

-1 0 1 2 -1 -4

Abi and Maddy see that you can make the following triplets:

-1 + -1 + 2
-1 + 0 + 1

For small sequences of numbers, the twins are comfortable using trial and error (ie. guess and check) to find triplets. Unfortunately, their father is mean and is giving them problems with larger sequences of numbers.

They would like your help in automating the process of searching for triplets using the magic of programming!

Input

You will be given a series of numbers, one sequence per line as shown below:

Example Input

-1 0 1 2 -1 -4

Output

For each sequence of numbers, print out all the triplets in ascending order:

Example Output

-1 + -1 + 2
-1 + 0 + 1

Note: Output the numbers in ascending order and ensure there is a single blank line between the outputs of each input sequence of numbers.

Programming Challenges

This problem is inspired by 3Sum on LeetCode.

Algorithmic Complexity

For each input test case, your solution should have the following targets:

Time Complexity O(2^N), where N is the length of each input sequence.
Space Complexity O(2^N), where N is the length of each input sequence.

Your solution may be below the targets, but it should not exceed them.

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge07               # Create and checkout challenge07 branch

$ $EDITOR challenge07/program.cpp           # Edit your code

$ git add challenge07/program.cpp           # Stage your changes
$ git commit -m "challenge07: done"         # Commit your changes

$ git push -u origin challenge07            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge07 program.cpp ...
  Result Success
    Time 0.12
   Score 6.00 / 6.00

$ curl -F source=@challenge07/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge07
{"result": "Success", "score": 6, "time": 0.11464905738830566, "value": 6, "status": 0}

Pull Request

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 04 TA List.


  1. Actually, not true. They do like math and are quite good at it. Probably get it from their mother.