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¶

``````\$ 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 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.