Imprime todas las formas posibles de escribir N como suma de dos o más números enteros positivos

Dado un número entero N , la tarea es imprimir todas las formas posibles en las que N se puede escribir como la suma de dos o más números enteros positivos.
Ejemplos: 
 

Entrada: N = 4 
Salida: 
1 1 1 1 
1 1 2 
1 3 
2 2 
Entrada: N = 3 
Salida: 
1 1 1 
1 2 
 

Enfoque: La idea es utilizar la recursividad para resolver este problema. La idea es considerar cada número entero de 1 a N tal que la suma N se pueda reducir por este número en cada llamada recursiva y si en cualquier llamada recursiva N se reduce a cero, imprimiremos la respuesta almacenada en el vector. A continuación se muestran los pasos para la recursividad: 
 

1. Obtenga el número N cuya suma debe dividirse en dos o más números enteros positivos.
2. Iterar recursivamente del valor 1 a N como índice i :

• Caso base: si el valor llamado recursivamente es 0 , imprima el vector actual, ya que esta es una de las formas de dividir N en dos o más enteros positivos. 
   

if (n == 0)
    printVector(arr);

• Llamada recursiva: si no se cumple el caso base, iterar recursivamente desde [i, N – i] . Empuje el elemento j actual en el vector (digamos arr ) e itere recursivamente para el siguiente índice y después de que finalice esta recursión, extraiga el elemento j insertado anteriormente: 
   

for j in range[i, N]:
    arr.push_back(j);
    recursive_function(arr, j + 1, N - j);
    arr.pop_back(j);   

A continuación se muestra la implementación del enfoque anterior:
 

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

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

1 1 1 1 
1 1 2 
1 3 
2 2

Complejidad de Tiempo: O(2 ^N ) 
Espacio Auxiliar: O(N ² )