How would I loop through an array and find any combination of numbers that adds up to equal a target number?

Question

I have thought about this issue a lot, and I have found a way to do it, but there has to be a better way. I want to enter a target number, then loop through an array and find any possible combination of numbers that adds up to equal that target number.

For example, I know this code works to find all combinations of two numbers that add up to equal the target number:

For i as Integer = 0 To MyArray.Length - 1
    For j as Integer = (i + 1) To MyArray.Length - 1
        If(MyArray(i) + MyArray(j)) = TargetNumber Then
            'Output these two numbers
        EndIf
    Next
Next

As you can see, this algorithm is designed only to get combinations of two numbers that add up to equal the target number. I know that I could nest another For loop (or as many as I want) to find as many numbers as I want to find, but there has to be a better, more efficient way. I don't want to have to nest another loop every time I want to find another number. Any suggestions? Should I avoid using arrays and try some other approach? Any help is appreciated.

@J3soon I'll be honest, recursion isn't my greatest skill. Could you post a suggestion? — ic3man7019, Dec 28 '15 at 13:53
if MyArray is `{1, 2}`, and input number is `3`, do you want to show the `1, 1, 1` combination? — J3soon, Dec 28 '15 at 13:56
If MyArray is {1,2,3,4,5} and TargetNumber = 10, the algorithm should output: (5+4+1), (1+2+3+4), (5+2+3) etc. — ic3man7019, Dec 28 '15 at 14:09
You are looking for [Partitions](https://en.wikipedia.org/wiki/Partition_%28number_theory%29). Already solved [HERE](http://stackoverflow.com/questions/400794/generating-the-partitions-of-a-number) — Alex B., Dec 28 '15 at 14:11
@AlexB. Thanks for the link. I don't exactly want partitions. Partitions express every possible combination of numbers that are less than or equal to the target number. I want those numbers to come from a predefined list, or array in this case. I have no need to know any combinations of numbers that do not involve numbers in the array. — ic3man7019, Dec 28 '15 at 14:16
Yes I know, but you could start with a partition and restrict it to your needs. I guess it will not be a huge problem to e.g. exclude certain values which are not in your array. — Alex B., Dec 28 '15 at 14:52
So the most straightforward and easy way is by using recursive, when `MyArray` doesn't contains many numbers. — J3soon, Dec 28 '15 at 15:01

J3soon · Accepted Answer · 2015-12-28T15:19:45.823

1

This wont repeat any number in the BasicNums array, and it means that only specified number can print out the number combination.

Code below:

Module Module1

    Dim BasicNums() As Integer = {1, 2, 3, 4, 5, 6, 7, 8}
    Dim nums As New List(Of Integer)
    Dim TargetNumber As Integer

    Sub Main()
        TargetNumber = Console.ReadLine()
        Recursion(0, 0, 0)  'start recursive
        Console.ReadLine()  'pause the console
    End Sub

    Sub Recursion(ByVal depth As Integer, ByVal start As Integer, ByVal count As Integer)
        'depth -> the recursion's depth (the 'for' count)
        'start -> where the next for starts
        'count -> current number count
        If count = TargetNumber Then
            'when [count] equals [TargetNumber] print the combination nums
            For j As Integer = 0 To nums.Count - 1
                Console.Write(nums(j) & " ")
            Next
            Console.Write(vbCrLf)
            Return
        ElseIf depth = BasicNums.Length - 1 Then
            'stop the recursion when the recursion meets the length of [BasicNums]
            Return
        End If
        For i As Integer = start To BasicNums.Length - 1
            nums.Add(BasicNums(i))
            Recursion(depth + 1, i + 1, count + BasicNums(i))
            nums.Remove(BasicNums(i))
        Next
    End Sub
End Module

Example Input:

Output:

edited Dec 28 '15 at 15:19

answered Dec 28 '15 at 14:50

J3soon

3,013
2
29
49

It appears that this will work. Could you explain your parameters for the `Recursive` function? – ic3man7019 Dec 28 '15 at 15:01
@J3son your solution grows exponentially which should be ok for the owners example of 10 numbers. – Alex B. Dec 28 '15 at 15:19
I've added some comments – J3soon Dec 28 '15 at 15:19
@AlexB.Yes, so the `Basicnums` length shouldn't be too long. – J3soon Dec 28 '15 at 15:21
@J3soon Thank you! This solution will prevent me from having to write a bunch of nested `For` loops, at least. If there is anyway that this function could be improved, please let me know. I think it is efficient enough to work in most cases, but I foresee some cases that will have many more numbers to try to add together. – ic3man7019 Dec 28 '15 at 15:23
@ic3man7019 It seems that you had unaccepted this answer. Is there any wrong parts in my answer? – J3soon Jan 01 '16 at 16:14

How would I loop through an array and find any combination of numbers that adds up to equal a target number?

1 Answers1