List Every Unique Quadruplet That Sums to a Target

Given an integer array nums and an integer target, find every combination of four different elements whose values add up to target, and report them with no duplicate quadruplet appearing twice — a quadruplet is a duplicate of another if it has the same four values, regardless of which indices produced them. Since the answer is checked as a single flat list of numbers, package your result the same way as the triplet version: sort the four values inside each quadruplet from smallest to largest, then arrange the quadruplets themselves from smallest to largest (comparing their first value, then second, then third, then fourth), and concatenate everything into one array.

Test Case 1:

Input:nums = [2, -1, 0, 3, -3, 1], target = 2

Output:[-3, 0, 2, 3, -1, 0, 1, 2]

Explanation:Two quadruplets sum to 2: (-3, 0, 2, 3) and (-1, 0, 1, 2). Each is sorted internally, the groups are ordered by their first value, then concatenated.

Test Case 2:

Input:nums = [0, 0, 0, 0], target = 0

Output:[0, 0, 0, 0]

Explanation:Only one unique quadruplet exists — all four zeros.

Test Case 3:

Input:nums = [1, 2, 3, 4], target = 100

Output:[]

Explanation:The largest possible sum here is 1+2+3+4=10, nowhere near 100 — the result is empty.

Constraints

◆4 ≤ nums.length ≤ 200
◆-10⁵ ≤ nums[i] ≤ 10⁵
◆-10⁵ ≤ target ≤ 10⁵

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (integers) — 4-10 integers, separated by commas or spaces.target

1	class Solution {
2	public int[] quadrupletsSummingToTarget(int[] nums, int target) {
3	Arrays.sort(nums);
4	List<Integer> result = new ArrayList<>();
5	int n = nums.length;
6	for (int i = 0; i < n - 3; i++) {
7	if (i > 0 && nums[i] == nums[i - 1]) continue;
8	for (int j = i + 1; j < n - 2; j++) {
9	if (j > i + 1 && nums[j] == nums[j - 1]) continue;
10	int left = j + 1, right = n - 1;
11	while (left < right) {
12	int sum = nums[i] + nums[j] + nums[left] + nums[right];
13	if (sum == target) {
14	result.add(nums[i]);
15	result.add(nums[j]);
16	result.add(nums[left]);
17	result.add(nums[right]);
18	left++;
19	right--;
20	while (left < right && nums[left] == nums[left - 1]) left++;
21	while (left < right && nums[right] == nums[right + 1]) right--;
22	} else if (sum < target) {
23	left++;
24	} else {
25	right--;
26	}
27	}
28	}
29	}
30	int[] flat = new int[result.size()];
31	for (int k = 0; k < flat.length; k++) flat[k] = result.get(k);
32	return flat;
33	}
34	}
35

-3

-1

0

1

2

3

0

1

2

3

4

5

INITIALIZE

nums = [2, -1, 0, 3, -3, 1], target = 2. Sorted, it becomes [-3, -1, 0, 1, 2, 3].

Step 1 / 31

Approach & Solutions

Brute Force — Four Nested Loops

Brute

Check every combination of four distinct indices with four nested loops. Whenever the four values sum to target, sort them and use a string key so the same quadruplet (by value) isn't recorded twice. Sort the collected quadruplets into the required order and flatten them into one array.

TimeO(n⁴)

SpaceO(n) for the dedupe set

Java

Try it out

class Solution {
    public int[] quadrupletsSummingToTarget(int[] nums, int target) {
        int n = nums.length;
        Set<String> seen = new HashSet<>();
        List<int[]> quads = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
                            int[] q = {nums[i], nums[j], nums[k], nums[l]};
                            Arrays.sort(q);
                            String key = q[0] + "," + q[1] + "," + q[2] + "," + q[3];
                            if (seen.add(key)) quads.add(q);
                        }
                    }
                }
            }
        }
        quads.sort((a, b) -> {
            for (int idx = 0; idx < 4; idx++) if (a[idx] != b[idx]) return a[idx] - b[idx];
            return 0;
        });
        int[] flat = new int[quads.size() * 4];
        int idx = 0;
        for (int[] q : quads) for (int v : q) flat[idx++] = v;
        return flat;
    }
}

Optimal — Sort + Nested Two Pointer

Optimal

Sort the array. Fix the first two numbers with two nested loops (each skipping repeats of its own previous value at the same nesting level), then sweep the remainder with two pointers exactly like the triplet version: match records the quadruplet and steps both pointers inward past duplicates, sum too small moves left up, sum too large moves right down.

TimeO(n³)

SpaceO(1) extra (excluding the sort and output)