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

Answer Source

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:

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