## Special quads

We are given an array of integers and asked to write a script to find the special quadruplets within the array. Special Quadruplets satisfy the following 2 rules:-- nums[a] + nums[b] + nums[c] == nums[d]

-- a < b < c < d

The obvious way to do this is with 4 nested loops:

$last = scalar(@nums) - 1;

for $a (0 .. $last - 3) {

for $b ($a + 1 .. $last - 2) {

for $c ($b + 1 .. $last - 1) {

for $d ($c + 1 .. $last) {

if ($nums[$a] + $nums[$b] + $nums[$c] == $nums[$d]) {

... we have an answer

The specification does not state whether the integers in the array are positive integers, but the examples contain only positive numbers. If negative numbers are to be allowed then I see no obvious way of optimising the above logic, but if we can assume that only positive integers are allowed then the task can be considerably speeded by:

- finding $max = the largest member of @nums

- abandoning the $b and $c searches if the sum so far exceeds $max:

for $b ($a + 1 .. $last - 2) {

**next if $nums[$a] + $nums[$b] > $max;**

for $c ($b + 1 .. $last - 1) {

**next if $nums[$a] + $nums[$b] + $nums[$c] > $max;**

for $d ($c + 1 .. $last) {

if ($nums[$a] + $nums[$b] + $nums[$c] == $nums[$d]) {

... we have an answer