3Sum
Real-world version: Charge Neutral TriplesThe statement here is our own: the same inputs, outputs and technique.
A physics teaching kit holds a tray of numbered beads. charges[i] is the electric charge carried by bead i, measured in elementary units, and it may be positive, negative or zero.
A neutral triple is a set of three beads sitting at three different positions in the tray whose charges add to zero.
Report the charge values of every neutral triple the tray allows. Ordering is irrelevant: the three values within a triple may be listed in any order, and the triples themselves may be listed in any order.
A combination of charge values may only be reported once. Beads at different positions can carry equal charges, and many bead sets can therefore land on the same three values, but they all describe one triple in your answer. A single bead may not fill two of the three slots of a triple.
Examples
Example 1
- Input
- charges = [-3, 1, 2, -1, 4, -1]
- Output
- [[-3, -1, 4], [-3, 1, 2], [-1, -1, 2]]
Three combinations settle to zero. The last one draws on both beads carrying -1, which is allowed because they sit at separate positions.
Example 2
- Input
- charges = [0, 0, 0, 0]
- Output
- [[0, 0, 0]]
Four beads can be picked three at a time in four ways, yet every pick lands on the same three charge values, so the answer holds one triple.
Example 3
- Input
- charges = [5, -2, 4]
- Output
- []
The only available set of three beads carries a total of 7, so nothing is reported.
Constraints
- 3 <= charges.length <= 3000
- -10^5 <= charges[i] <= 10^5
The groups you return, and the values inside each group, may be in any order.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def charge_neutral_triples(charges: list[int]) -> list[list[int]]:public List<List<Integer>> chargeNeutralTriples(int[] charges)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's