Struggling with nested for loop

Question

Given a main number and a subset of numbers, wanting to find all the possible combinations of the subset numbers that add up to the main number. e.g.:

INPUT

Main: 10
Subset: 2, 3, 5, 7

OUTPUT

Results: 3 + 7 = 10, 2 + 3 + 5 = 10
** Note: 5 + 5 = 10 would not be a valid result. **

Here is where I'm at so far:

// Main traversal
for (int a = 0; a < nums.Length; a++)
{
    sum = a;

    for (int b = a + 1; b < nums.Length; b++)
    {
      // Thinking this should be the loop that determines 
      // how many numbers are added together. 
      // e.g. Sum of 2 numbers, sum of 3 numbers, etc
        for (int c = a + 1; c < nums.Length; c++)
        {
            sum += nums[b + c];
        }
        if (sum == mainNumber)
            result += "Match found!\n";
    }
}

I am mainly struggling to understand the 'for loops.' I tried to find a 'for loop' visualizer but no luck. Alternatively, would recursion make this problem any easier to solve?

Recursion almost never makes a problem easier to understand :) — Michael Dorgan, Dec 21 '16 at 20:04
As to a visualizer, place print statements right below each of your for loops and print the values of `a` , `b`, and `c` in each location. That should help you `trace` what your code is actually doing and may help you better visualize it. — Michael Dorgan, Dec 21 '16 at 20:05
Or just attach the debugger.... More realistically, you are trying to do a combinatorics generator; I would look at creating *that* and evaluating the results (I *think* there is one built into .NET) — BradleyDotNET, Dec 21 '16 at 20:06
The problem with debuggers is that it doesn't leave a nice history of what just happened, which makes it harder when learning. They are great for now state, but not as much for past state. — Michael Dorgan, Dec 21 '16 at 20:07
@MichaelDorgan you should try out historical debugging in the latest Visual Studio — Blorgbeard, Dec 21 '16 at 20:09
Here is a question like yours with an valid answer :) The answer itself is quite complicated as I think it could be done simpler but it's working http://stackoverflow.com/questions/16604985/find-elements-in-a-list-that-together-add-up-to-a-target-number?noredirect=1&lq=1 — Nico, Dec 21 '16 at 20:09
[Finding all possible combinations of numbers to reach a given sum](http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum) — Mário Moura da Silva, Dec 21 '16 at 20:09
Side note: it is good idea to estimate number of results before writing code - in this case you need to check 2^n sets which clearly can not be done with n*n loop iterations... — Alexei Levenkov, Dec 21 '16 at 20:43
Are you struggling with understanding the concept of nested for loops in general, or understanding how to use them to solve this problem? — PartlyCloudy, Dec 21 '16 at 20:49

Cullub · Accepted Answer · 2016-12-21T20:57:13.180

Think of for loops as circles. Nested loops are like circles within circles.

Thankfully, you situation isn't nearly as complicated as this one. In this picture, the one large circle around is a for loop that is only true once. While inside that for loop, other loops were true multiple times. Each different size circle is a different loop.

I've rewritten your code with slightly more descriptive names, and with the sole purpose of explaining the loops - I took all the "useful" stuff out, and put console.writeline statements instead.

 // I'm using 5 as an example check here.
for (int outerLoopCounter = 0; outerLoopCounter < 5; outerLoopCounter++)
{
    Console.WriteLine("OUTER:             {0}", outerLoopCounter);

    for (int middleLoopCounter = 0; middleLoopCounter < 5; middleLoopCounter++)
    {
        Console.WriteLine("MIDDLE:              {0}", middleLoopCounter);

        for (int innerLoopCounter = 0; innerLoopCounter < 5; innerLoopCounter++)
        {
            Console.WriteLine("INNER:                 {0}", innerLoopCounter);
        }
    }
}

The Output is as follows:

OUTER:             0
MIDDLE:              0
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              1
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              2
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              3
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              4
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
OUTER:             1
MIDDLE:              0
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              1
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              2
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              3
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              4
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
OUTER:             2
MIDDLE:              0
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              1
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              2
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              3
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              4
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
OUTER:             3
MIDDLE:              0
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              1
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              2
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              3
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              4
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
OUTER:             4
MIDDLE:              0
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              1
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              2
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              3
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4
MIDDLE:              4
INNER:                 0
INNER:                 1
INNER:                 2
INNER:                 3
INNER:                 4

If you look at the indentation, you can see a pattern. The numbers closest to the text (to the left) are outputted from the outer loop. The middle ones come from the middle loop, and the furthest to the right numbers come from the innermost loop.

As you can see, the outer loop is slowly revolving, counting to four (0, 1, 2, 3, 4), until it is no longer less than five, at which point it exits the loop. The middle circle (loop) is counting slightly faster. It gets to four once (again, 0-4) every time that the outer loop increments by one. And the inner circle is revolving quite quickly - it counts to four and exits each time the middle circle increments.

Struggling with nested for loop

INPUT

OUTPUT

1 Answers1