Print all possible ways to write N as sum of two or more positive integers
Given an integer N, the task is to print all the possible ways in which N can be written as the sum of two or more positive integers.
Examples:
Input: N = 4
Output:
1 1 1 1
1 1 2
1 3
2 2
Input: N = 3
Output:
1 1 1
1 2
Approach: The idea is to use recursion to solve this problem. The idea is to consider every integer from 1 to N such that the sum N can be reduced by this number at each recursive call and if at any recursive call N reduces to zero then we will print the answer stored in the vector. Below are the steps for recursion:
- Get the number N whose sum has to be broken into two or more positive integers.
- Recursively iterate from value 1 to N as index i:
- Base Case: If the value called recursively is 0, then print the current vector as this is one of the ways to broke N into two or more positive integers.
if (n == 0) printVector(arr);
- Recursive Call: If the base case is not met, then Recursively iterate from [i, N – i]. Push the current element j into vector(say arr) and recursively iterate for the next index and after this recursion ends then pop the element j inserted previously:
for j in range[i, N]: arr.push_back(j); recursive_function(arr, j + 1, N - j); arr.pop_back(j);
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the values stored // in vector arr void printVector(vector< int >& arr) { if (arr.size() != 1) { // Traverse the vector arr for ( int i = 0; i < arr.size(); i++) { cout << arr[i] << " " ; } cout << endl; } } // Recursive function to print different // ways in which N can be written as // a sum of at 2 or more positive integers void findWays(vector< int >& arr, int i, int n) { // If n is zero then print this // ways of breaking numbers if (n == 0) printVector(arr); // Start from previous element // in the representation till n for ( int j = i; j <= n; j++) { // Include current element // from representation arr.push_back(j); // Call function again // with reduced sum findWays(arr, j, n - j); // Backtrack to remove current // element from representation arr.pop_back(); } } // Driver Code int main() { // Given sum N int n = 4; // To store the representation // of breaking N vector< int > arr; // Function Call findWays(arr, 1, n); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to print the values stored // in vector arr static void printVector(ArrayList<Integer> arr) { if (arr.size() != 1 ) { // Traverse the vector arr for ( int i = 0 ; i < arr.size(); i++) { System.out.print(arr.get(i) + " " ); } System.out.println(); } } // Recursive function to print different // ways in which N can be written as // a sum of at 2 or more positive integers static void findWays(ArrayList<Integer> arr, int i, int n) { // If n is zero then print this // ways of breaking numbers if (n == 0 ) printVector(arr); // Start from previous element // in the representation till n for ( int j = i; j <= n; j++) { // Include current element // from representation arr.add(j); // Call function again // with reduced sum findWays(arr, j, n - j); // Backtrack to remove current // element from representation arr.remove(arr.size() - 1 ); } } // Driver code public static void main(String[] args) { // Given sum N int n = 4 ; // To store the representation // of breaking N ArrayList<Integer> arr = new ArrayList<Integer>(); // Function call findWays(arr, 1 , n); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to print the values stored # in vector arr def printVector(arr): if ( len (arr) ! = 1 ): # Traverse the vector arr for i in range ( len (arr)): print (arr[i], end = " " ) print () # Recursive function to print different # ways in which N can be written as # a sum of at 2 or more positive integers def findWays(arr, i, n): # If n is zero then print this # ways of breaking numbers if (n = = 0 ): printVector(arr) # Start from previous element # in the representation till n for j in range (i, n + 1 ): # Include current element # from representation arr.append(j) # Call function again # with reduced sum findWays(arr, j, n - j) # Backtrack to remove current # element from representation del arr[ - 1 ] # Driver Code if __name__ = = '__main__' : # Given sum N n = 4 # To store the representation # of breaking N arr = [] # Function Call findWays(arr, 1 , n) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to print the values stored // in vector arr static void printList(List< int > arr) { if (arr.Count != 1) { // Traverse the vector arr for ( int i = 0; i < arr.Count; i++) { Console.Write(arr[i] + " " ); } Console.WriteLine(); } } // Recursive function to print different // ways in which N can be written as // a sum of at 2 or more positive integers static void findWays(List< int > arr, int i, int n) { // If n is zero then print this // ways of breaking numbers if (n == 0) printList(arr); // Start from previous element // in the representation till n for ( int j = i; j <= n; j++) { // Include current element // from representation arr.Add(j); // Call function again // with reduced sum findWays(arr, j, n - j); // Backtrack to remove current // element from representation arr.RemoveAt(arr.Count - 1); } } // Driver code public static void Main(String[] args) { // Given sum N int n = 4; // To store the representation // of breaking N List< int > arr = new List< int >(); // Function call findWays(arr, 1, n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Function to print the values stored // in vector arr function printVector(arr) { if (arr.length != 1) { // Traverse the vector arr for ( var i = 0; i < arr.length; i++) { document.write( arr[i] + " " ); } document.write( "<br>" ); } } // Recursive function to print different // ways in which N can be written as // a sum of at 2 or more positive integers function findWays(arr, i, n) { // If n is zero then print this // ways of breaking numbers if (n == 0) printVector(arr); // Start from previous element // in the representation till n for ( var j = i; j <= n; j++) { // Include current element // from representation arr.push(j); // Call function again // with reduced sum findWays(arr, j, n - j); // Backtrack to remove current // element from representation arr.pop(); } } // Driver Code // Given sum N var n = 4; // To store the representation // of breaking N var arr = []; // Function Call findWays(arr, 1, n); </script> |
Output:
1 1 1 1 1 1 2 1 3 2 2
Time Complexity: O(2N)
Auxiliary Space: O(N2)
Contact Us