Iteration

Lesson

A common type of problem is to find all possible sets of numbers that sum to a target. Here's an example of this:

**Problem:** Print out all positive integers `a`

, `b`

, and `c`

that sum to the number 10.

$\notag
\large \texttt{a + b + c = 10}$

You might think to do a brute force solution like this:

Time Complexity $O(n^3)$. We have a triple for-loop.

Space Complexity $O(1)$.

But you can actually do much better than brute-force. Whenever you see a problem like this, you can always write one of the variables using the other variables. Here, you can subtract a and b from both sides of the equation to solve for c, like this:

$\notag
\large \texttt{c = 10 - a - b}$

This equation tells you that the value of `c`

is completely determined by the values of `a`

and `b`

. This is because `c = 10 - a - b`

. This means we don't need to loop over it. Here's the above code, but where we removed the for-loop over c:

Time Complexity $O(n^2)$. We have a double for-loop.

Space Complexity $O(1)$.

Mark as Completed: