Найдите все различные четверки в массиве, которые в сумме дают заданное значение

Дан массив arr[] , состоящий из N целых чисел и целого числа K , задача состоит в том, чтобы напечатать все возможные уникальные четверки (arr[i], arr[j], arr[k], arr[l]) , сумма которых равна K таких что все их индексы различны.

Примеры:

Input: arr[] = {1, 0, -1, 0, -2, 2}, K = 0
Output:
-2 -1 1 2
-2 0 0 2
-1 0 0 1
Explanation:
Below are the quadruplets whose sum is K (= 0):

• {-2, -1, 1, 2}
• {-2, 0, 0, 2}
• {-1, 0, 0, 1}

Input: arr[] = {1, 2, 3, -1}, target = 5
Output:
1 2 3 -1

Наивный подход: самый простой подход состоит в том, чтобы сгенерировать все возможные четверки из заданного массива arr[] и, если сумма элементов четверок равна K , затем вставить текущие четверки в HashSet, чтобы избежать подсчета дубликатов четверок. После проверки всех четверок распечатайте все четверки, хранящиеся в HashSet.

Временная сложность: O(N ⁴ )
Вспомогательное пространство: O(N ⁴ )

Эффективный подход. Приведенный выше подход также можно оптимизировать, используя идею создания всех возможных пар данного массива. Выполните указанные шаги, чтобы решить проблему:

• Инициализируйте HashMap , скажем, в котором хранятся все возможные четверки.
• Инициализируйте HashMap, скажем, M , который хранит сумму всех возможных пар данного массива с их соответствующими индексами.
• Сгенерируйте все возможные пары данного массива и сохраните сумму всех пар элементов (arr[i], arr[j]) с их индексами (i, j) в HashMap M .
• Теперь снова сгенерируйте все возможные пары данного массива и для каждой суммы всех пар элементов (arr[i], arr[j]) , если значение (K – sum) существует в HashMap M , затем сохраните текущие четверки в HashMap .
• После выполнения вышеуказанных шагов распечатайте все четверки, хранящиеся в HashMap ans .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² * log N)
Вспомогательное пространство: O(N ² )