 ic3man7019 - 4 years ago 193
Vb.net Question

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

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. Anonymous

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()
Recursion(0, 0, 0)  'start recursive
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
Recursion(depth + 1, i + 1, count + BasicNums(i))
nums.Remove(BasicNums(i))
Next
End Sub
End Module
``````

Example Input:

``````7
``````

Output:

``````1 2 4
1 6
2 5
3 4
7
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download