Question

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

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
fn print_array(arr: &[i32], size: usize) {
    let mut line = String::new();

    for i in 0..size {
        if i > 0 {
            line.push_str(" + ");   // add plus signs between numbers
        }
        line.push_str(&arr[i].to_string());
    }

    println!("{}", line);
}

/*
    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.
*/
fn partitions(arr: &mut [i32], size: usize, start: i32, remaining: i32) {

    // Base case: exact sum reached
    if remaining == 0 {
        if size >= 2 {      // enforce "two or more integers"
            print_array(arr, size);
        }
        return;
    }

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

fn main() {
    let n: i32 = 5;                 // number to partition
    let mut arr = [0i32; 128];      // holds current partition (large enough buffer)

    partitions(&mut 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

fn partitions(n: usize) -> Vec<Vec<usize>> {
    // Inner recursive function that builds partitions.
    // remaining — how much is left to sum to n
    // start — the minimum next value allowed (enforces non-decreasing order)
    // current — the partial partition being built
    // result — all completed partitions
    fn backtrack(
        remaining: usize,
        start: usize,
        current: &mut Vec<usize>,
        result: &mut Vec<Vec<usize>>,
    ) {
        // If nothing is left, we found a valid partition
        if remaining == 0 {
            result.push(current.clone()); // clone because current will be modified later
            return;
        }

        // Try all possible next values from `start` up to `remaining`
        for i in start..=remaining {
            current.push(i);                 // choose i
            backtrack(remaining - i, i, current, result); // recurse with reduced remainder
            current.pop();                   // undo the choice (backtrack)
        }
    }

    let mut result = Vec::new();
    let mut current = Vec::new();

    // Start building partitions with minimum allowed value = 1
    backtrack(n, 1, &mut current, &mut result);

    result
}

fn main() {
    let n = 5;
    for p in partitions(n) {
        println!("{:?}", p);
    }
}


/*
run:

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]

*/

 

70+ SQL courses for beginners and professionals