Задача №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 kSum($nums, $target, 4);
}

function kSum($nums, $target, $k) {
$res = [];

if (!count($nums)) {
return $res;
}

$averageValue = $target / $k;
if ($averageValue < $nums[0] || $nums[count($nums)-1] < $averageValue) {
return $res;
}

if ($k == 2) {
return $this->twoSum($nums, $target);
}

for ($i = 0; $i < count($nums); $i++) {
if ($i == 0 || $nums[$i - 1] != $nums[$i]) {
$kSum = $this->kSum(array_slice($nums, $i+1), $target - $nums[$i], $k - 1);
foreach ($kSum as $item) {
$res[] = array_merge([$nums[$i]], $item);
}
}
}
return $res;
}

function twoSum($nums, $target) {
$res = [];
$lo = 0;
$hi = count($nums) - 1;

while ($lo < $hi) {
$currSum = $nums[$lo] + $nums[$hi];
if ($currSum < $target || ($lo > 0 && $nums[$lo] == $nums[$lo - 1])) {
$lo++;
} elseif ($currSum > $target || ($hi < count($nums) - 1 && $nums[$hi] == $nums[$hi + 1])) {
$hi--;
} else {
$res[] = [$nums[$lo], $nums[$hi]];
$lo++;
$hi--;
}
}
return $res;
}
}

Ставь 👍 и забирай 📚 Базу знаний