打印可以组成给定数字的所有点的组合-yiteyi-C++库

你可以赢得三种篮球分数，1分、2分和3分。如果总分为n，打印出所有组合，组成n。

null

例如：

For n = 1, the program should print following:1For n = 2, the program should print following:1 12For n = 3, the program should print following:1 1 11 22 1 3For n = 4, the program should print following:1 1 1 11 1 21 2 11 32 1 12 23 1and so on ...

算法：

在第一个位置，我们可以有三个数字1、2或3。
首先，将1放在第一个位置，递归调用n-1。
然后把2放在第一个位置，递归调用n-2。
然后把3放在第一个位置，递归调用n-3。
如果n变为0，那么我们形成了一个组合，组成n，所以打印当前组合。

下面是一个通用的实现。在下面的实现中，如果篮球比赛中有更高的分数（超过3分），我们可以更改MAX_POINT。

C++

                         // 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"                                     ;                       
                                                 printCompositions(n, 0);                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by rathbhupendra                       

C

                         // 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                                     (                                     ""                                     );                       
                         }                       
           
                         /* Driver function to test above functions */                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 5;                       
                                   
                                                 printf                                     (                                     "Different compositions formed by 1, 2 and 3 of %d are"                                     , n);                       
                                                 printCompositions(n, 0);                       
                                   
                                                 getchar                                     ();                       
                                                 return                                     0;                       
                         }                       

JAVA

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

蟒蛇3

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

                         // 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                       
                         // 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                                     ""                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 5;                       
           
                         echo                                     "Different compositions formed"                                     .                       
                                                 " by 1, 2 and 3 of "                                     .                                     $n                                     .                                     " are"                                     ;                       
                         printCompositions(                                     $n                                     , 0);                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

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

输出：

Different compositions formed by 1, 2 and 3 of 5 are1 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

如果您在上述代码/算法中发现任何错误，请写下评论，或者寻找其他方法来解决相同的问题。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章