Question

How to find all possible ways to write a positive integer as a sum of positive integers in VB.NET

Answer 1

Imports System
				
Module Program

    ' Print a partition stored in 'arr' in the form "a + b + c"
    Sub PrintArray(arr() As Integer, size As Integer)
        For i As Integer = 0 To size - 1
            If i > 0 Then Console.Write(" + ")   ' add plus signs between numbers
            Console.Write(arr(i))
        Next
        Console.WriteLine()
    End Sub

    '
    '    Generate all partitions of a number using non-decreasing sequences.
    '
    '    arr       – current partial partition being built
    '    size      – how many elements are currently in arr
    '    start     – the smallest number allowed next (prevents duplicates like 2+1 vs 1+2)
    '    remaining – how much is left to reach the target sum
    '
    '    When remaining == 0, arr contains a complete valid partition.
    '
    Sub Partitions(arr() As Integer, size As Integer, start As Integer, remaining As Integer)

        ' Base case: exact sum reached
        If remaining = 0 Then
            If size >= 2 Then      ' enforce "two or more integers"
                PrintArray(arr, size)
            End If
            Return
        End If

        ' Try all next values from 'start' up to 'remaining'
        For j As Integer = start To remaining
            arr(size) = j                          ' choose j
            Partitions(arr, size + 1, j, remaining - j)  ' recurse with reduced remainder
            ' no need to "pop" in VB.NET; we just overwrite next time
        Next
    End Sub

    Sub Main()
        Dim n As Integer = 5          ' number to partition
        Dim arr(128) As Integer       ' holds current partition (large enough buffer)

        Partitions(arr, 0, 1, n)      ' start with smallest allowed value = 1
    End Sub

End Module


'
' run:
'
' 1 + 1 + 1 + 1 + 1
' 1 + 1 + 1 + 2
' 1 + 1 + 3
' 1 + 2 + 2
' 1 + 4
' 2 + 3
'

 

70+ SQL courses for beginners and professionals

Answer 2

Imports System
Imports System.Collections.Generic

Module IntegerPartitions

    ' Generate all ways to write a positive integer n
    ' as a sum of positive integers (integer partitions).
    '
    ' Example for n = 5:
    ' [
    '   [ 5 ],
    '   [ 4, 1 ],
    '   [ 3, 2 ],
    '   [ 3, 1, 1 ],
    '   [ 2, 2, 1 ],
    '   [ 2, 1, 1, 1 ],
    '   [ 1, 1, 1, 1, 1 ]
    ' ]

    ' Function that returns all partitions of n
    Function Partitions(n As Integer) As List(Of List(Of Integer))
        Dim results As New List(Of List(Of Integer))()
        Backtrack(n, n, New List(Of Integer)(), results)
        Return results
    End Function

    ' Backtracking helper function
    Sub Backtrack(remaining As Integer,
                  maxValue As Integer,
                  current As List(Of Integer),
                  results As List(Of List(Of Integer)))

        ' If nothing remains, we found a valid partition
        If remaining = 0 Then
            results.Add(New List(Of Integer)(current))
            Exit Sub
        End If

        ' Try next numbers from maxValue down to 1
        For nextValue As Integer = Math.Min(remaining, maxValue) To 1 Step -1
            current.Add(nextValue) ' choose
            Backtrack(remaining - nextValue, nextValue, current, results) ' explore
            current.RemoveAt(current.Count - 1) ' un-choose (backtrack)
        Next
    End Sub

    Sub Main()
        Dim result = Partitions(5)

        Console.WriteLine("[")
        For i = 0 To result.Count - 1
            Console.Write("  [ ")
            For j = 0 To result(i).Count - 1
                Console.Write(result(i)(j))
                If j < result(i).Count - 1 Then Console.Write(", ")
            Next
            Console.Write(" ]")
            If i < result.Count - 1 Then
                Console.WriteLine(",")
            Else
                Console.WriteLine()
            End If
        Next
        Console.WriteLine("]")
    End Sub

End Module


' run:
'
' [
'  [ 5 ],
'  [ 4, 1 ],
'  [ 3, 2 ],
'  [ 3, 1, 1 ],
'  [ 2, 2, 1 ],
'  [ 2, 1, 1, 1 ],
'  [ 1, 1, 1, 1, 1 ]
' ]
'

 

70+ SQL courses for beginners and professionals