4 sum-coding question asked by Cognizant, Microsoft, Twitter, Adobe

Problem Statement:

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n

a, b, c, and d are distinct.

nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Input Format:

Array of numbers

Output Format:

Array of quadraplets

Sample Input 1:

nums = [1,0,-1,0,-2,2], target = 0

Sample Output 1:

[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Sample Input 2:

nums = [2,2,2,2,2], target = 8

Sample Output 2:

[[2,2,2,2]]

Constraint:

• 1 <= nums.length <= 200
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

Approach:

The approach lies in problem pattern of 2-sum and 3-sum (check them out on placewit.medium.com).

The two pointers pattern requires the array to be sorted, so we do that first. Also, it’s easier to deal with duplicates if the array is sorted: repeated values are next to each other and easy to skip.

For 3Sum, we enumerate each value in a single loop, and use the two pointers pattern for the rest of the array. For kSum, we will have k - 2 nested loops to enumerate all combinations of k - 2 values.

We can implement k - 2 loops using a recursion. We will pass the starting point and k as the parameters. When k == 2, we will call twoSum, terminating the recursion.

The above approach can be applied for any sort of k-sum problem.

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.