# List the combinations that add up to 0 from a vector of numbers

I'm writing a function that, given a Vec<i32> of numbers, lists the combinations that add up to 0. The code works, but it feels amateurish.

Specifically, the inside of the loop looks really ugly -- there must be a simpler way of doing this that avoids unwrap() and the repetition. Maybe with match?

fn calc_zer(input: Vec<i32>) -> Vec<(i32, i32, i32)> {
let mut output: Vec<(i32, i32, i32)> = Vec::new();
for a in (0..input.len() - 2) {
for b in (a+1..input.len() -1) {
for c in (b+1..input.len()) {
if (input.get(a).unwrap() + input.get(b).unwrap() + input.get(c).unwrap() == 0) {
output.push((*input.get(a).unwrap(), *input.get(b).unwrap(), *input.get(c).unwrap()));
}
}
}
}
output
}


1. Rust is a statically-compiled language, which means you get warnings and errors at compile time. Don't ignore those:

warning: unnecessary parentheses around for head expression
--> src/main.rs:3:14
|
3 |     for a in (0..input.len() - 2) {
|              ^^^^^^^^^^^^^^^^^^^^
|
= note: #[warn(unused_parens)] on by default

warning: unnecessary parentheses around for head expression
--> src/main.rs:4:18
|
4 |         for b in (a+1..input.len() -1) {
|                  ^^^^^^^^^^^^^^^^^^^^^
|
= note: #[warn(unused_parens)] on by default

warning: unnecessary parentheses around for head expression
--> src/main.rs:5:22
|
5 |             for c in (b+1..input.len()) {
|                      ^^^^^^^^^^^^^^^^^^
|
= note: #[warn(unused_parens)] on by default

warning: unnecessary parentheses around if condition
--> src/main.rs:6:20
|
6 |                 if (input.get(a).unwrap() + input.get(b).unwrap() + input.get(c).unwrap() == 0) {
|                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: #[warn(unused_parens)] on by default

2. Next, run Clippy to get even more automated suggestions. Note that this contains the answer to your question:

warning: this argument is passed by value, but not consumed in the function body
--> src/main.rs:1:24
|
1 | pub fn calc_zer(input: Vec<i32>) -> Vec<(i32, i32, i32)> {
|                        ^^^^^^^^ help: consider changing the type to &[i32]
|
= note: #[warn(needless_pass_by_value)] on by default
= help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#needless_pass_by_value

warning: called .get().unwrap() on a Vec. Using [] is more clear and more concise
--> src/main.rs:6:20
|
6 |                 if input.get(a).unwrap() + input.get(b).unwrap() + input.get(c).unwrap() == 0 {
|                    ^^^^^^^^^^^^^^^^^^^^^ help: try this &input[a]
|
= note: #[warn(get_unwrap)] on by default
= help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#get_unwrap

3. Extract local variables so you don't even have the overhead of accessing the array multiple times.

4. There's no reason to provide an explicit type for output - it will be inferred from the return value.

5. Extract a variable for input.len() since that never changes during the iteration.

6. It's almost always better to iterate over the collection directly instead of indexing it. We can also use Iterator::enumerate to get the index as we go along.

This yields

fn calc_zer(input: &[i32]) -> Vec<(i32, i32, i32)> {
let mut output = Vec::new();

let len = input.len();

for (a_i, &a) in input[0..len - 2].iter().enumerate() {
for (b_i, &b) in input[a_i + 1..len - 1].iter().enumerate() {
for &c in &input[a_i + b_i + 2..len] {
if a + b + c == 0 {
output.push((a, b, c));
}
}
}
}

output
}


This is a bit ugly, and even worse — I got it wrong originally! See the revision history for details. This was caused because enumerate starts counting from zero, even though we are iterating through an offset into the original vector.

However, Rust has a strong emphasis on reusing code via crates. In this example, I turn to one of my favorites — itertools:

extern crate itertools;

use itertools::Itertools;

fn calc_zer(input: &[i32]) -> Vec<(i32, i32, i32)> {
input.iter()
.tuple_combinations()
.filter(|&(a, b, c)| a + b + c == 0)
.map(|(&a, &b, &c)| (a, b, c))
.collect()
}


• The first implementation is incorrect. It will return results like (-2, 1, 1) from the input [-2, -1, 0, 1, 2]. The reason is that x..y-z != x..y - z (yes you can subtract from Range). You need less spaces or more parenthesis :) – jacwah Jul 15 '17 at 1:49
• @jacwah it certainly was incorrect, thank you for pointing that out. However, you can not subtract from Range! You gave me a scare there, as I wasn't sure how I'd never seen that before; good thing it doesn't exist ^_^. – Shepmaster Jul 15 '17 at 2:02
• Hmm, what's going on here?? It's fairily uninuitive that spacing should make difference in the first place. – jacwah Jul 15 '17 at 3:03
• @jacwah that's good then because spacing is not the problem. The problem is the enumerate call starting at zero. – Shepmaster Jul 15 '17 at 3:10
• Oh I feel stupid now. I was testing a bunch of versions of calc_zer and just for fun tried changing the spacing, and I thought it worked. I must have run the wrong function. Thanks for clearing that up! – jacwah Jul 15 '17 at 3:13

Let's do some complexity analysis! Your algorithm searches all combinations ${n \choose 3}$ which is cubic time. We can improve this by sorting and being smarter about which triplets we visit.

For instance, say we have the the vector [-2, -1, 0, 1, 2]. We start by looking at (-2, -1, 2), whose sum is less than zero. Thus, we can rule out all (-2, -1, x) triplets since all remaining x are less than 2.

fn calc_zer(input_slice: &[i32]) -> Vec<(i32, i32, i32)> {
let mut input = input_slice.to_vec();
input.sort();
let mut output = Vec::new();

for i in 0..input.len() - 1 {
let mut l = i + 1;
let mut r = input.len() - 1;

while l < r {
let sum = input[i] + input[l] + input[r];

if sum == 0 {
output.push((input[i], input[l], input[r]));
l += 1;
r -= 1;
} else if sum < 0 {
l += 1;
} else {
r -= 1;
}
}
}

output
}


Here is the code, adapted from the GeeksForGeeks article linked below. It goes through each element, matches it with a (smallest, largest) pair and adjusts the pair if the sum is negative or positive.

This algorithm spends $O(n \lg n)$ time sorting and $O(n)$ time per element (the while loop), which yields a quadratic time complexity.

I compared the two algorithms by running them on a 1000 element input. The cubic algorithm took 4 minutes. The quadratic half a second.

Resources:

Shepmaster's solution with Itertools is fine (I assume it works) and may be the best way to go, in an absolute sense, but I don't believe it's the answer you were looking for. If you're still learning Rust you probably aren't familiar enough with the standard libraries to even know about tuple_combinations(). I think you wanted to fix your implementation rather than replace it with another. The fact that the other may somehow be better doesn't seem to be the point here.

Your gut told you, "the inside of the loop looks really ugly -- there must be a simpler way of doing this that avoids unwrap() and the repetition", so that's what I'll address.

uglyness: You have a lot of code that doesn't need to be there. Most of it is the unwrap() calls. Eliminating them will improve things. You don't need to declare a type for output since it's the return type—that may not always be true but it is here.

unwrap(): Why use get()? You have a vector (better yet, a slice) which supports indexing via [ ] notation. Boom—no more unwrap().

This is what I belive your solution should be:

pub fn calc_zer(input: &[i32]) -> Vec<(i32, i32, i32)> {
let mut output = Vec::new();
let end = input.len();
for a in 0..end-2 {
for b in a+1..end-1 {
for c in b+1..end {
let x = (input[a], input[c], input[c]);
if x.0 + x.1 + x.2 == 0 { output.push(x); }
}
}
}
output
}


The only improvement I can claim is subjective; clarity. It's visually neat and tidy. There is less code to read, less to understand. That makes it easier to edit. That could support a claim of less error prone, but it's arguable.