// https://leetcode.com/problems/4sum
fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
    val targetLong = target.toLong()
    val quardruplets = mutableSetOf<Quardruplet>()
    nums.sort()
    for (first in 0..nums.lastIndex - 3) {
        for (second in first + 1..nums.lastIndex - 2) {
            var third = second + 1
            var fourth = nums.lastIndex
            while (third < fourth) {
                val sum = nums[first].toLong() + nums[second] + nums[third] + nums[fourth]
                if (sum == targetLong) {
                    quardruplets.add(Quardruplet(nums[first], nums[second], nums[third], nums[fourth]))
                    third++
                    fourth--
                } else if (sum > target) {
                    fourth--
                } else {
                    third++
                }
            }
        }
    }
    return quardruplets.toList().map { listOf(it.first, it.second, it.third, it.fourth) }
}

data class Quardruplet(val first: Int, val second: Int, val third: Int, val fourth: Int)

// https://leetcode.com/problems/4sum
fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
    val targetLong = target.toLong()
    val quardruplets = mutableSetOf<Quardruplet>()
    nums.sort()
    for (first in 0..nums.lastIndex - 3) {
        for (second in first + 1..nums.lastIndex - 2) {
            var third = second + 1
            var fourth = nums.lastIndex
            while (third < fourth) {
                val sum = nums[first].toLong() + nums[second] + nums[third] + nums[fourth]
                if (sum == targetLong) {
                    quardruplets.add(Quardruplet(nums[first], nums[second], nums[third], nums[fourth]))
                    third++
                    fourth--
                } else if (sum > target) {
                    fourth--
                } else {
                    third++
                }
            }
        }
    }
    return quardruplets.toList().map { listOf(it.first, it.second, it.third, it.fourth) }
}

data class Quardruplet(val first: Int, val second: Int, val third: Int, val fourth: Int)
