Imprime todas las combinaciones de puntos que pueden componer un número dado

Puedes ganar tres tipos de puntos de baloncesto, 1 punto, 2 puntos y 3 puntos. Dada una puntuación total de n, imprima todas las combinaciones para componer n. 

Ejemplos:

For n = 1, the program should print following:
1

For n = 2, the program should print following:
1 1
2

For n = 3, the program should print following:
1 1 1
1 2
2 1 
3

For n = 4, the program should print following:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

and so on ...

Algoritmo: 

1. En la primera posición, podemos tener tres números 1 o 2 o 3.
2. Primero, coloque 1 en la primera posición y llame recursivamente a n-1.
3. Luego coloque 2 en la primera posición y recursivamente solicite n-2.
4. Luego coloque 3 en la primera posición y recursivamente solicite n-3.
5. Si n se convierte en 0, entonces hemos formado una combinación que compone n, así que imprima la combinación actual.

A continuación se muestra una implementación generalizada. En la implementación a continuación, podemos cambiar MAX_POINT si hay puntos más altos (más de 3) en el juego de baloncesto.  

// C++ program to Print all
// combinations of points that
// can compose a given number
#define MAX_POINT 3
#define ARR_SIZE 100
#include <bits/stdc++.h>
using namespace std;
 
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);
 
/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initial value of i must be passed as 0 */
void printCompositions(int n, int i)
{
 
    /* array must be static as we want to keep track
    of values stored in arr[] using current calls of
    printCompositions() in function call stack*/
    static int arr[ARR_SIZE];
     
    if (n == 0)
    {
        printArray(arr, i);
    }
    else if(n > 0)
    {
        int k;
        for (k = 1; k <= MAX_POINT; k++)
        {
            arr[i]= k;
            printCompositions(n-k, i+1);
        }
    }
}
 
/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
    int i;
    for (i = 0; i < arr_size; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
}
 
/* Driver code */
int main()
{
    int n = 5;
     
    cout<<"Different compositions formed by 1, 2 and 3 of "<<n<<" are\n";
    printCompositions(n, 0);
    return 0;
}
 
// This code is contributed by rathbhupendra

// C program to Print all
// combinations of points that
// can compose a given number
#define MAX_POINT 3
#define ARR_SIZE 100
#include<stdio.h>
 
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size);
 
/* The function prints all combinations of numbers 1, 2, ...MAX_POINT
that sum up to n.
i is used in recursion keep track of index in arr[] where next
element is to be added. Initial value of i must be passed as 0 */
void printCompositions(int n, int i)
{
 
    /* array must be static as we want to keep track
    of values stored in arr[] using current calls of
    printCompositions() in function call stack*/
    static int arr[ARR_SIZE];
     
    if (n == 0)
    {
        printArray(arr, i);
    }
    else if(n > 0)
    {
        int k;
        for (k = 1; k <= MAX_POINT; k++)
        {
        arr[i]= k;
        printCompositions(n-k, i+1);
        }
    }
}
 
/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
void printArray(int arr[], int arr_size)
{
    int i;
    for (i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
/* Driver function to test above functions */
int main()
{
    int n = 5;
     
    printf("Different compositions formed by 1, 2 and 3 of %d are\n", n);
    printCompositions(n, 0);
     
    getchar();
    return 0;
}

// Java program to Print all
// combinations of points that
// can compose a given number
import java.io.*;
 
class GFG
{
    // Function prints all combinations of numbers 1, 2, ...MAX_POINT
    // that sum up to n.
    // i is used in recursion keep track of index in arr[] where next
    // element is to be added. Initial value of i must be passed as 0
    static void printCompositions(int arr[], int n, int i)
    {
        int MAX_POINT = 3;
        if (n == 0)
        {
            printArray(arr, i);
        }
        else if(n > 0)
        {
            for (int k = 1; k <= MAX_POINT; k++)
            {
                arr[i]= k;
                printCompositions(arr, n-k, i+1);
            }
        }
    }
     
    // Utility function to print array arr[]
    static void printArray(int arr[], int m)
    {
        for (int i = 0; i < m; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
     
     
    // Driver program
    public static void main (String[] args)
    {
        int n = 5;
        int size = 100;
        int[] arr = new int[size];
        System.out.println("Different compositions formed by 1, 2 and 3 of "+ n + " are");
        printCompositions(arr, n, 0);
    }
}
 
// Contributed by Pramod Kumar

# Python3 program to Print all combinations
# of points that can compose a given number
MAX_POINT = 3;
ARR_SIZE = 100;
 
arr = [0] * ARR_SIZE;
 
# The function prints all combinations
# of numbers 1, 2, ...MAX_POINT that sum
# up to n. i is used in recursion keep
# track of index in arr[] where next
# element is to be added. Initial value
# of i must be passed as 0
def printCompositions(n, i):
     
    # array must be static as we
    # want to keep track of values
    # stored in arr[] using current
    # calls of printCompositions() in
    # function call stack*/
    if (n == 0):
        printArray(arr, i);
    elif(n > 0):
        for k in range(1,MAX_POINT + 1):
            arr[i] = k;
            printCompositions(n - k, i + 1);
 
# UTILITY FUNCTIONS */
# Utility function to print array arr[] */
def printArray(arr, arr_size):
    for i in range(arr_size):
        print(arr[i], end = " ");
    print();
 
# Driver Code
n = 5;
print("Different compositions formed " +
         "by 1, 2 and 3 of", n, " are");
printCompositions(n, 0);
 
# This code is contributed by mits

// C# program to Print all
// combinations of points that
// can compose a given number
using System;
 
class GFG {
     
    // Function prints all combinations of numbers
    // 1, 2, ...MAX_POINT that sum up to n. i is
    // used in recursion keep track of index in
    // arr[] where next element is to be added.
    // Initial value of i must be passed as 0
    static void printCompositions(int[] arr, int n, int i)
    {
        int MAX_POINT = 3;
        if (n == 0) {
            printArray(arr, i);
        }
        else if (n > 0) {
            for (int k = 1; k <= MAX_POINT; k++) {
                arr[i] = k;
                printCompositions(arr, n - k, i + 1);
            }
        }
    }
 
    // Utility function to print array arr[]
    static void printArray(int[] arr, int m)
    {
        for (int i = 0; i < m; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
 
    // Driver program
    public static void Main()
    {
        int n = 5;
        int size = 100;
        int[] arr = new int[size];
         
        Console.WriteLine("Different compositions formed"
                    + " by 1, 2 and 3 of " + n + " are");
        printCompositions(arr, n, 0);
    }
}
 
// Contributed by Sam007

<?php
// PHP program to Print all
// combinations of points that
// can compose a given number
$MAX_POINT = 3;
$ARR_SIZE = 100;
 
$arr = array($ARR_SIZE);
 
/* The function prints all combinations
of numbers 1, 2, ...MAX_POINT that sum
up to n. i is used in recursion keep
track of index in arr[] where next
element is to be added. Initial value
of i must be passed as 0 */
function printCompositions($n, $i)
{
    global $arr, $MAX_POINT, $ARR_SIZE;
     
    /* array must be static as we
    want to keep track of values
    stored in arr[] using current
    calls of printCompositions() in
    function call stack*/
    if ($n == 0)
    {
        printArray($arr, $i);
    }
    else if($n > 0)
    {
        for ($k = 1; $k <= $MAX_POINT; $k++)
        {
            $arr[$i] = $k;
            printCompositions($n - $k, $i + 1);
        }
    }
}
 
/* UTILITY FUNCTIONS */
/* Utility function to print array arr[] */
function printArray($arr, $arr_size)
{
    for ($i = 0; $i < $arr_size; $i++)
        echo $arr[$i]." ";
    echo "\n";
}
 
// Driver Code
$n = 5;
 
echo "Different compositions formed" .
     " by 1, 2 and 3 of ".$n." are\n";
printCompositions($n, 0);
 
// This code is contributed by mits
?>

<script>
 
// Javascript program to print all
// combinations of points that
// can compose a given number
 
// Function prints all combinations of numbers
// 1, 2, ...MAX_POlet that sum up to n.
// i is used in recursion keep track of index
// in arr[] where next element is to be added.
// Initial value of i must be passed as 0
function printCompositions(arr, n, i)
{
    let MAX_POINT = 3;
    if (n == 0)
    {
        printArray(arr, i);
    }
    else if(n > 0)
    {
        for(let k = 1; k <= MAX_POINT; k++)
        {
            arr[i] = k;
            printCompositions(arr, n - k, i + 1);
        }
    }
}
 
// Utility function to print array arr[]
function printArray(arr, m)
{
    for(let i = 0; i < m; i++)
        document.write(arr[i] + " ");
         
    document.write("<br/>");
}
 
// Driver code
let n = 5;
let size = 100;
let arr = new Array(size).fill(0);
 
document.write("Different compositions formed " +
               "by 1, 2 and 3 of "+ n + " are" + "<br/>");
printCompositions(arr, n, 0);
 
// This code is contributed by avijitmondal1998
 
</script>

Producción: 

Different compositions formed by 1, 2 and 3 of 5 are
1 1 1 1 1 
1 1 1 2 
1 1 2 1 
1 1 3 
1 2 1 1 
1 2 2 
1 3 1 
2 1 1 1 
2 1 2 
2 2 1 
2 3 
3 1 1 
3 2 

Complejidad del tiempo: O(3 ⁿ )

Espacio Auxiliar: O(n)

Escriba comentarios si encuentra algún error en el código/algoritmo anterior, o encuentre otras formas de resolver el mismo problema.