3Sum With Multiplicity: Counting Combinations

May 24, 20266 min read

leetcodeproblemmediumarrayshash-maptwo-pointers

LeetCode 3Sum With Multiplicity (problem 923, medium) asks you to count the number of index tuples (i, j, k) where i < j < k and arr[i] + arr[j] + arr[k] == target. The twist compared to regular 3Sum: duplicates are allowed, and you need to count all valid index combinations, not just unique value triples. Return the count modulo 10^9 + 7.

The problem

Given an integer array arr and an integer target, return the number of tuples (i, j, k) such that i < j < k and arr[i] + arr[j] + arr[k] == target. Since the answer can be very large, return it modulo 10^9 + 7.

Key constraint: values in arr are between 0 and 100 inclusive. This bounded value range is the clue that points toward a frequency-based approach.

Example: arr = [1,1,2,2,3,3,4,4,5,5], target = 8. There are 20 valid tuples total.

Count the frequency of each value, then enumerate all value triples (a, b, c) where a + b + c = target. Use combinatorics to compute the number of index tuples for each value triple.

Why the brute force fails

A naive triple loop checks all O(n^3) index combinations. With n up to 3000, that is 27 billion operations. Way too slow.

You could optimize with sorting and two pointers to get O(n^2), which works for n = 3000. But there is an even better approach that takes advantage of the bounded value range.

The key insight: frequency counting plus combinatorics

Since array values are between 0 and 100, there are at most 101 distinct values. Instead of iterating over indices, you can:

Count the frequency of each value in the array.
Iterate over all possible value triples (a, b, c) where a + b + c == target and a <= b <= c.
For each valid triple, compute how many index tuples it contributes using combinatorics.

The combinatorics depend on whether values repeat within the triple:

All distinct (a < b < c): contribution is freq[a] * freq[b] * freq[c]
Two equal (a == b != c): contribution is C(freq[a], 2) * freq[c], which is freq[a] * (freq[a] - 1) / 2 * freq[c]
Two equal (a != b == c): contribution is freq[a] * C(freq[b], 2), which is freq[a] * freq[b] * (freq[b] - 1) / 2
All three equal (a == b == c): contribution is C(freq[a], 3), which is freq[a] * (freq[a] - 1) * (freq[a] - 2) / 6

This runs in O(W^2) where W = 101, which is essentially constant time after the initial frequency count.

Practice this pattern

The code

def threeSumMulti(arr, target):
    MOD = 10**9 + 7
    count = [0] * 101
    for x in arr:
        count[x] += 1
    ans = 0
    for i in range(101):
        for j in range(i, 101):
            k = target - i - j
            if k < j or k > 100:
                continue
            if i == j == k:
                ans += count[i] * (count[i] - 1) * (count[i] - 2) // 6
            elif i == j:
                ans += count[i] * (count[i] - 1) // 2 * count[k]
            elif j == k:
                ans += count[i] * count[j] * (count[j] - 1) // 2
            else:
                ans += count[i] * count[j] * count[k]
    return ans % MOD

Here is what each piece does:

Build a frequency array count where count[v] is the number of times value v appears in arr.
Iterate over all pairs (i, j) with i <= j. Compute k = target - i - j. If k < j or k > 100, skip (we only want i <= j <= k to avoid double-counting).
Based on how many of i, j, k are equal, apply the appropriate combinatorial formula.
Return the total modulo 10^9 + 7.

The constraint k >= j ensures each unordered value triple is counted exactly once. The combinatorial formulas then account for all valid orderings of indices.

The condition k = target - i - j with k >= j means you never need a third nested loop. You compute k directly and check if it is in range. This is what makes the solution O(W^2) instead of O(W^3).

Walking through the combination counting

Let's trace through arr = [1,1,2,2,3,3,4,4,5,5] with target = 8. After counting frequencies, we have freq[1] = freq[2] = freq[3] = freq[4] = freq[5] = 2.

Step 1: Triple (1, 2, 5). All distinct values.

All three values are different, so every combination of one 1, one 2, and one 5 works. That gives 2 * 2 * 2 = 8 tuples.

Step 2: Triple (1, 3, 4). All distinct values.

Same structure as step 1. Three distinct values, each appearing twice. Another 8 tuples.

Step 3: Triple (2, 2, 4). Two values are equal (a == b).

Since a == b == 2, we choose 2 indices from the 2 available positions for value 2. That is C(2,2) = 1. Multiply by freq[4] = 2. Total: 1 * 2 = 2 tuples.

Step 4: Triple (2, 3, 3). Two values are equal (b == c).

Since b == c == 3, we choose 2 indices from the 2 positions for value 3. That is C(2,2) = 1. Multiply by freq[2] = 2. Total: 2 * 1 = 2 tuples.

Total count

8 + 8 + 2 + 2 = 20

Sum all contributions from every valid (a, b, c) triple. Return the total modulo 10^9 + 7.

The total across all valid triples gives us the final answer (modulo 10^9 + 7).

Drill this with spaced repetition

Complexity analysis

Metric	Value
Time	O(n + W^2), where W = 101 (the value range). O(n) for frequency counting, O(W^2) for iterating over value pairs
Space	O(W), for the frequency array of size 101

The O(n + W^2) time is effectively O(n) since W^2 = 10201 is a constant. For n = 3000, this is much faster than the O(n^2) two-pointer approach.

Building blocks

This problem combines two reusable building blocks that show up across many LeetCode problems.

Frequency counting

Convert an array of values into a frequency map, then operate on the frequencies instead of the raw elements. This works whenever values are bounded or when you care about "how many" rather than "which indices."

The same pattern appears in problems like Two Sum (using a complement lookup), Group Anagrams (character frequency as key), and Majority Element (frequency tracking).

Combinatorial counting

When you need to count arrangements rather than enumerate them, use combinatorial formulas. Choosing k items from n is C(n, k) = n! / (k! * (n-k)!). For small k values (2 or 3), the formulas simplify to multiplication and division.

This pattern shows up in problems like Unique Paths (grid path counting), Combinations (generating C(n,k) subsets), and any problem where brute-force enumeration is too slow but the count follows a mathematical formula.

Edge cases

All elements are the same. For example, arr = [0, 0, 0, 0], target = 0. The answer is C(4, 3) = 4. Your i == j == k branch handles this.
Target is unreachable. If target > 300 (max possible sum is 100 + 100 + 100), the answer is 0. The k > 100 check naturally skips everything.
Large array with few distinct values. For example, 3000 elements all being 1 and 2. The frequency approach shines here because W^2 stays small regardless of n.
Overflow concerns. freq[i] * (freq[i] - 1) * (freq[i] - 2) can be large when frequencies are in the thousands. In Python this is fine (arbitrary precision), but in other languages you would need to apply the modulo during computation.
Single valid triple. If only one value combination works (for example target = 3 with the array containing exactly one 1, one 1, and one 1), the formula still applies correctly.

From understanding to recall

The frequency counting plus combinatorics approach is elegant, but there are details that trip people up under pressure. When do you use C(n, 2) versus straight multiplication? How do you avoid double-counting triples? What is the loop structure that ensures i <= j <= k?

The answer is to practice the two building blocks separately. If you can write a frequency count from memory and you understand when to apply C(n, 2) versus C(n, 3), the full solution assembles itself. You are not memorizing one monolithic algorithm. You are combining two small patterns you already own.

Spaced repetition locks these patterns into long-term memory. You write the frequency count loop, then the combinatorial case analysis, then the full solution. After a few rounds at increasing intervals, the structure is automatic. You see "count tuples with bounded values" and the approach clicks without hesitation.

3Sum - The classic sorted two-pointer approach for finding triples that sum to zero
3Sum Closest - Variation using distance tracking instead of exact matching
4Sum II - Hash map counting for four arrays, a similar "count combinations" flavor

CodeBricks breaks the 3Sum With Multiplicity problem into its frequency counting and combinatorial building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a counting problem shows up in your interview, you do not think about it. You just write it.

Try CodeBricks free