Triangle side

Question

how get triangle sides with given sum of sides for example

sum = 12
sides = 4 4 4 or 5 4 3 or 5 5 2

complexity less than n^2

Answer 1

This is similar to the three sum problem:
https://en.wikipedia.org/wiki/3SUM

You should be able to get under O(n^2):

"In 2014, the original 3SUM conjecture was refuted by Allan Grønlund and Seth Pettie who gave a deterministic algorithm that solves 3SUM in O(n^2/((log n}/{log log n})^(2/3))) time"

However, more work would be required to determine that.

Just found this variation on the Wikipedia page:

"Non-zero sum

Instead of looking for numbers whose sum is 0, it is possible to look for numbers whose sum is any constant C in the following way:

Subtract C/3 from all elements of the input array.
In the modified array, find 3 elements whose sum is 0.

For e.g., if A=[1,2,3,4] and if you are asked to find 3sum for C=4, then subtract all the elements of A by 4/3 and solve it in the usual 3sum way, i.e., (a-C/3) + (b-C/3) + (c-C/3) = 0"

Answer 2

I don't think you can go under n^2, because the output can have size which is O(n^2).