Problem

Given a 0-indexed integer array nums, return the number ofdistinct quadruplets (a, b, c, d) such that:

  • nums[a] + nums[b] + nums[c] == nums[d], and
  • a < b < c < d

Examples

Example 1

1
2
3

Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.

Example 2

1
2
3

Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].

Example 3

1
2
3
4
5
6
7

Input: nums = [1,1,1,3,5]
Output: 4
Explanation: The 4 quadruplets that satisfy the requirement are:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

Constraints

  • 4 <= nums.length <= 50
  • 1 <= nums[i] <= 100

Solution

Method 1 – Brute Force Enumeration

Intuition

Since the array is small (n ≤ 50), we can check all quadruplets (a, b, c, d) with a < b < c < d and count those where nums[a] + nums[b] + nums[c] == nums[d].

Approach

  1. Initialize ans = 0.
  2. For all quadruplets (a, b, c, d) with a < b < c < d:
    1. If nums[a] + nums[b] + nums[c] == nums[d], increment ans.
  3. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int a = 0; a < n; ++a)
            for (int b = a+1; b < n; ++b)
                for (int c = b+1; c < n; ++c)
                    for (int d = c+1; d < n; ++d)
                        if (nums[a] + nums[b] + nums[c] == nums[d])
                            ans++;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func countQuadruplets(nums []int) int {
    n, ans := len(nums), 0
    for a := 0; a < n; a++ {
        for b := a+1; b < n; b++ {
            for c := b+1; c < n; c++ {
                for d := c+1; d < n; d++ {
                    if nums[a]+nums[b]+nums[c] == nums[d] {
                        ans++
                    }
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int countQuadruplets(int[] nums) {
        int n = nums.length, ans = 0;
        for (int a = 0; a < n; a++)
            for (int b = a+1; b < n; b++)
                for (int c = b+1; c < n; c++)
                    for (int d = c+1; d < n; d++)
                        if (nums[a] + nums[b] + nums[c] == nums[d])
                            ans++;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun countQuadruplets(nums: IntArray): Int {
        val n = nums.size
        var ans = 0
        for (a in 0 until n)
            for (b in a+1 until n)
                for (c in b+1 until n)
                    for (d in c+1 until n)
                        if (nums[a] + nums[b] + nums[c] == nums[d])
                            ans++
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def countQuadruplets(self, nums: list[int]) -> int:
        n, ans = len(nums), 0
        for a in range(n):
            for b in range(a+1, n):
                for c in range(b+1, n):
                    for d in range(c+1, n):
                        if nums[a] + nums[b] + nums[c] == nums[d]:
                            ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn count_quadruplets(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for a in 0..n {
            for b in a+1..n {
                for c in b+1..n {
                    for d in c+1..n {
                        if nums[a] + nums[b] + nums[c] == nums[d] {
                            ans += 1;
                        }
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    countQuadruplets(nums: number[]): number {
        const n = nums.length;
        let ans = 0;
        for (let a = 0; a < n; a++)
            for (let b = a+1; b < n; b++)
                for (let c = b+1; c < n; c++)
                    for (let d = c+1; d < n; d++)
                        if (nums[a] + nums[b] + nums[c] === nums[d])
                            ans++;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^4), since we check all quadruplets.
  • 🧺 Space complexity: O(1), only a counter is used.