# Ways to write n as sum of two or more positive integers

For a given number n > 0, find the number of different ways in which n can be written as a sum of at two or more positive integers.

Examples:

```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
```

This problem can be solved in the similar fashion as coin change problem, the difference is only that in this case we should iterate for 1 to n-1 instead of particular values of coin as in coin-change problem.

## C/C++

 `// Program to find the number of ways, n can be ` `// written as sum of two or more positive integers. ` `#include ` `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 consturcted 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 = 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

## Java

 `// 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 consturcted 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. `

## Python

 `# 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 consturcted 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 `

## C#

 `// 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 consturcted 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 = 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

 ` `

Output:

```14
```

Time complexity O(n2)

## tags:

Dynamic Programming Dynamic Programming