Question

How to find all possible ways to write a positive integer as a sum of positive integers in C#

Answer 1

using System;

class Program
{

    // Print a partition stored in 'arr' in the form "a + b + c"
    static void PrintArray(int[] arr, int size)
    {
        for (int i = 0; i < size; i++) {
            if (i > 0) Console.Write(" + ");   // add plus signs between numbers
            Console.Write(arr[i]);
        }
        Console.WriteLine();
    }

    /*
        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.
    */
    static void Partitions(int[] arr, int size, int start, int remaining)
    {
        // Base case: exact sum reached
        if (remaining == 0) {
            if (size >= 2)      // enforce "two or more integers"
                PrintArray(arr, size);
            return;
        }

        // Try all next values from 'start' up to 'remaining'
        for (int j = start; j <= remaining; j++) {
            arr[size] = j;                          // choose j
            Partitions(arr, size + 1, j, remaining - j);  // recurse with reduced remainder
            // no need to "pop" in C#; we just overwrite next time
        }
    }

    static void Main()
    {
        int n = 5;                 // number to partition
        int[] arr = new int[128];  // holds current partition (large enough buffer)

        Partitions(arr, 0, 1, n);  // start with smallest allowed value = 1
    }
}


/*
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

using System;
using System.Collections.Generic;

class 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
    static List<List<int>> Partitions(int n)
    {
        var results = new List<List<int>>();
        Backtrack(n, n, new List<int>(), results);
        return results;
    }

    /*
        Backtracking helper function.

        remaining - how much is left to reach n
        maxValue  - maximum allowed next number (keeps order non-increasing)
        current   - current partial partition
        results   - list of all partitions
    */
    static void Backtrack(int remaining, int maxValue, List<int> current, List<List<int>> results)
    {
        // If nothing remains, we found a valid partition
        if (remaining == 0) {
            results.Add(new List<int>(current));
            return;
        }

        // Try next numbers from maxValue down to 1
        for (int next = Math.Min(remaining, maxValue); next >= 1; next--) {
            current.Add(next); // choose
            Backtrack(remaining - next, next, current, results); // explore
            current.RemoveAt(current.Count - 1); // un-choose (backtrack)
        }
    }

    static void Main()
    {
        var result = Partitions(5);

        Console.WriteLine("[");
        for (int i = 0; i < result.Count; i++) {
            Console.Write("  [ ");
            for (int j = 0; j < result[i].Count; j++) {
                Console.Write(result[i][j]);
                if (j < result[i].Count - 1)
                    Console.Write(", ");
            }
            Console.Write(" ]");

            if (i < result.Count - 1)
                Console.WriteLine(",");
            else
                Console.WriteLine();
        }
        Console.WriteLine("]");
    }
}



/*
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