Formas de escribir n como suma de dos o más números enteros positivos

Para un número dado n > 0, encuentre el número de formas diferentes en las que n puede escribirse como una suma de dos o más enteros positivos.
Ejemplos: 
 

Input : n = 5
Output : 6
Explanation : All possible six ways are :
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Input : 4
Output : 4
Explanation : All possible four ways are :
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Este problema se puede resolver de manera similar al problema de cambio de moneda , la diferencia es que en este caso debemos iterar de 1 a n-1 en lugar de valores particulares de moneda como en el problema de cambio de moneda.

// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
#include <bits/stdc++.h>
using namespace std;
 
// Returns number of ways to write n as sum of
// two or more positive integers
int countWays(int n)
{
    // table[i] will be storing the number of
    // solutions for value i. We need n+1 rows
    // as the table is constructed in bottom up
    // manner using the base case (n = 0)
    int table[n+1];
 
    // Initialize all table values as 0
    memset(table, 0, sizeof(table));
 
    // Base case (If given value is 0)
    table[0] = 1;
 
    // Pick all integer one by one and update the
    // table[] values after the index greater
    // than or equal to n
    for (int i=1; i<n; i++)
        for (int j=i; j<=n; j++)
            table[j] += table[j-i];
 
    return table[n];
}
 
// Driver program
int main()
{
    int n = 7;
    cout << countWays(n);
    return 0;
}

// Program to find the number of ways,
// n can be written as sum of two or
// more positive integers.
import java.util.Arrays;
 
class GFG {
     
    // Returns number of ways to write
    // n as sum of two or more positive
    // integers
    static int countWays(int n)
    {
         
        // table[i] will be storing the
        // number of solutions for value
        // i. We need n+1 rows as the
        // table is constructed in bottom
        // up manner using the base case
        // (n = 0)
        int table[] = new int[n + 1];
     
        // Initialize all table values as 0
        Arrays.fill(table, 0);
     
        // Base case (If given value is 0)
        table[0] = 1;
     
        // Pick all integer one by one and
        // update the table[] values after
        // the index greater than or equal
        // to n
        for (int i = 1; i < n; i++)
            for (int j = i; j <= n; j++)
                table[j] += table[j - i];
     
        return table[n];
    }
     
    //driver code
    public static void main (String[] args)
    {
        int n = 7;
         
        System.out.print(countWays(n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Program to find the number of ways, n can be
# written as sum of two or more positive integers.
 
# Returns number of ways to write n as sum of
# two or more positive integers
def CountWays(n):
 
    # table[i] will be storing the number of
    # solutions for value i. We need n+1 rows
    # as the table is constructed in bottom up
    # manner using the base case (n = 0)
    # Initialize all table values as 0
    table =[0] * (n + 1)
 
    # Base case (If given value is 0)
    # Only 1 way to get 0 (select no integer)
    table[0] = 1
 
    # Pick all integer one by one and update the
    # table[] values after the index greater
    # than or equal to n
    for i in range(1, n ):
 
        for j in range(i , n + 1):
 
            table[j] +=  table[j - i]           
 
    return table[n]
 
# driver program
def main():
 
    n = 7
 
    print (CountWays(n))
 
if __name__ == '__main__':
    main()
 
#This code is contributed by Neelam Yadav

// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
using System;
 
class GFG {
     
    // Returns number of ways to write n as sum of
    // two or more positive integers
    static int countWays(int n)
    {
         
        // table[i] will be storing the number of
        // solutions for value i. We need n+1 rows
        // as the table is constructed in bottom up
        // manner using the base case (n = 0)
        int []table = new int[n+1];
      
        // Initialize all table values as 0
        for(int i = 0; i < table.Length; i++)
            table[i] = 0;
      
        // Base case (If given value is 0)
        table[0] = 1;
      
        // Pick all integer one by one and update the
        // table[] values after the index greater
        // than or equal to n
        for (int i = 1; i < n; i++)
            for (int j = i; j <= n; j++)
                table[j] += table[j-i];
      
        return table[n];
    }
     
    //driver code
    public static void Main()
    {
        int n = 7;
         
        Console.Write(countWays(n));
    }
}
 
// This code is contributed by Anant Agarwal.

<?php
// Program to find the number of ways, n can be
// written as sum of two or more positive integers.
 
// Returns number of ways to write n as sum
// of two or more positive integers
function countWays($n)
{
    // table[i] will be storing the number of
    // solutions for value i. We need n+1 rows
    // as the table is constructed in bottom up
    // manner using the base case (n = 0)
    $table = array_fill(0, $n + 1, NULL);
 
    // Base case (If given value is 0)
    $table[0] = 1;
 
    // Pick all integer one by one and update
    // the table[] values after the index
    // greater than or equal to n
    for ($i = 1; $i < $n; $i++)
        for ($j = $i; $j <= $n; $j++)
            $table[$j] += $table[$j - $i];
 
    return $table[$n];
}
 
// Driver Code
$n = 7;
echo countWays($n);
 
// This code is contributed by ita_c
?>

<script>
     
    function countWays(n)
    {
        // table[i] will be storing the
        // number of solutions for value
        // i. We need n+1 rows as the
        // table is constructed in bottom
        // up manner using the base case
        // (n = 0)
        let table = new Array(n + 1);
       
        // Initialize all table values as 0
        for(let i = 0; i < n + 1; i++)
        {
            table[i]=0;
        }
       
        // Base case (If given value is 0)
        table[0] = 1;
       
        // Pick all integer one by one and
        // update the table[] values after
        // the index greater than or equal
        // to n
        for (let i = 1; i < n; i++)
            for (let j = i; j <= n; j++)
                table[j] += table[j - i];
       
        return table[n];
    }
     
    let n = 7;
    document.write(countWays(n));
     
    // This code is contributed by avanitrachhadiya2155
</script>

Producción: 
 

14

Complejidad del tiempo O(n ² )
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.