Dado un número positivo, encuentra todas las combinaciones de números positivos que suman ese número. El programa debe imprimir solo combinaciones, no permutaciones. Por ejemplo, para la entrada 3, se debe imprimir 1, 2 o 2, 1.
Ejemplos:
Input: N = 3 Output: 1 1 1 1 2 3 Input: N = 5 Output: 1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 1 4 2 3 5
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
La idea es usar la recursividad. Usamos una array para almacenar combinaciones y llenamos recursivamente la array y recursimos con un número reducido. La invariante utilizada en la solución es que cada combinación siempre se almacenará en orden creciente de elementos involucrados. De esa manera podemos evitar la impresión de permutaciones.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find out all combinations of
// positive numbers that add upto given number
#include <iostream>
using namespace std;
/* arr - array to store the combination
index - next location in array
num - given number
reducedNum - reduced number */
void findCombinationsUtil(int arr[], int index,
int num, int reducedNum)
{
// Base condition
if (reducedNum < 0)
return;
// If combination is found, print it
if (reducedNum == 0)
{
for (int i = 0; i < index; i++)
cout << arr[i] << " ";
cout << endl;
return;
}
// Find the previous number stored in arr[]
// It helps in maintaining increasing order
int prev = (index == 0)? 1 : arr[index-1];
// note loop starts from previous number
// i.e. at array location index - 1
for (int k = prev; k <= num ; k++)
{
// next element of array is k
arr[index] = k;
// call recursively with reduced number
findCombinationsUtil(arr, index + 1, num,
reducedNum - k);
}
}
/* Function to find out all combinations of
positive numbers that add upto given number.
It uses findCombinationsUtil() */
void findCombinations(int n)
{
// array to store the combinations
// It can contain max n elements
int arr[n];
//find all combinations
findCombinationsUtil(arr, 0, n, n);
}
// Driver code
int main()
{
int n = 5;
findCombinations(n);
return 0;
}
Java
// Java program to find out
// all combinations of positive
// numbers that add upto given
// number
import java.io.*;
class GFG
{
/* arr - array to store the
combination
index - next location in array
num - given number
reducedNum - reduced number */
static void findCombinationsUtil(int arr[], int index,
int num, int reducedNum)
{
// Base condition
if (reducedNum < 0)
return;
// If combination is
// found, print it
if (reducedNum == 0)
{
for (int i = 0; i < index; i++)
System.out.print (arr[i] + " ");
System.out.println();
return;
}
// Find the previous number
// stored in arr[]. It helps
// in maintaining increasing
// order
int prev = (index == 0) ?
1 : arr[index - 1];
// note loop starts from
// previous number i.e. at
// array location index - 1
for (int k = prev; k <= num ; k++)
{
// next element of
// array is k
arr[index] = k;
// call recursively with
// reduced number
findCombinationsUtil(arr, index + 1, num,
reducedNum - k);
}
}
/* Function to find out all
combinations of positive
numbers that add upto given
number. It uses findCombinationsUtil() */
static void findCombinations(int n)
{
// array to store the combinations
// It can contain max n elements
int arr[] = new int [n];
// find all combinations
findCombinationsUtil(arr, 0, n, n);
}
// Driver code
public static void main (String[] args)
{
int n = 5;
findCombinations(n);
}
}
// This code is contributed
// by akt_mit
Python3
# Python3 program to find out all
# combinations of positive
# numbers that add upto given number
# arr - array to store the combination
# index - next location in array
# num - given number
# reducedNum - reduced number
def findCombinationsUtil(arr, index, num,
reducedNum):
# Base condition
if (reducedNum < 0):
return
# If combination is
# found, print it
if (reducedNum == 0):
for i in range(index):
print(arr[i], end = " ")
print("")
return
# Find the previous number stored in arr[].
# It helps in maintaining increasing order
prev = 1 if(index == 0) else arr[index - 1]
# note loop starts from previous
# number i.e. at array location
# index - 1
for k in range(prev, num + 1):
# next element of array is k
arr[index] = k
# call recursively with
# reduced number
findCombinationsUtil(arr, index + 1, num,
reducedNum - k)
# Function to find out all
# combinations of positive numbers
# that add upto given number.
# It uses findCombinationsUtil()
def findCombinations(n):
# array to store the combinations
# It can contain max n elements
arr = [0] * n
# find all combinations
findCombinationsUtil(arr, 0, n, n)
# Driver code
n = 5;
findCombinations(n);
# This code is contributed by mits
C#
// C# program to find out all
// combinations of positive numbers
// that add upto given number
using System;
class GFG
{
/* arr - array to store the
combination
index - next location in array
num - given number
reducedNum - reduced number */
static void findCombinationsUtil(int []arr, int index,
int num, int reducedNum)
{
// Base condition
if (reducedNum < 0)
return;
// If combination is
// found, print it
if (reducedNum == 0)
{
for (int i = 0; i < index; i++)
Console.Write (arr[i] + " ");
Console.WriteLine();
return;
}
// Find the previous number
// stored in arr[]. It helps
// in maintaining increasing
// order
int prev = (index == 0) ?
1 : arr[index - 1];
// note loop starts from
// previous number i.e. at
// array location index - 1
for (int k = prev; k <= num ; k++)
{
// next element of
// array is k
arr[index] = k;
// call recursively with
// reduced number
findCombinationsUtil(arr, index + 1, num,
reducedNum - k);
}
}
/* Function to find out all
combinations of positive
numbers that add upto given
number. It uses findCombinationsUtil() */
static void findCombinations(int n)
{
// array to store the combinations
// It can contain max n elements
int []arr = new int [n];
// find all combinations
findCombinationsUtil(arr, 0, n, n);
}
// Driver code
static public void Main ()
{
int n = 5;
findCombinations(n);
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// PHP program to find out all
// combinations of positive
// numbers that add upto given number
/* arr - array to store the combination
index - next location in array
num - given number
reducedNum - reduced number */
function findCombinationsUtil($arr, $index,
$num, $reducedNum)
{
// Base condition
if ($reducedNum < 0)
return;
// If combination is
// found, print it
if ($reducedNum == 0)
{
for ($i = 0; $i < $index; $i++)
echo $arr[$i] , " ";
echo "\n";
return;
}
// Find the previous number
// stored in arr[] It helps
// in maintaining increasing order
$prev = ($index == 0) ? 1 : $arr[$index - 1];
// note loop starts from previous
// number i.e. at array location
// index - 1
for ($k = $prev; $k <= $num ; $k++)
{
// next element of array is k
$arr[$index] = $k;
// call recursively with
// reduced number
findCombinationsUtil($arr, $index + 1,
$num, $reducedNum - $k);
}
}
/* Function to find out all
combinations of positive numbers
that add upto given number.
It uses findCombinationsUtil() */
function findCombinations($n)
{
// array to store the combinations
// It can contain max n elements
$arr = array();
//find all combinations
findCombinationsUtil($arr, 0, $n, $n);
}
// Driver code
$n = 5;
findCombinations($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find out
// all combinations of positive
// numbers that add upto given
// number
/* arr - array to store the
combination
index - next location in array
num - given number
reducedNum - reduced number */
function findCombinationsUtil(arr, index,
num, reducedNum)
{
// Base condition
if (reducedNum < 0)
return;
// If combination is
// found, print it
if (reducedNum == 0)
{
for (let i = 0; i < index; i++)
document.write (arr[i] + " ");
document.write("<br/>");
return;
}
// Find the previous number
// stored in arr[]. It helps
// in maintaining increasing
// order
let prev = (index == 0) ?
1 : arr[index - 1];
// note loop starts from
// previous number i.e. at
// array location index - 1
for (let k = prev; k <= num ; k++)
{
// next element of
// array is k
arr[index] = k;
// call recursively with
// reduced number
findCombinationsUtil(arr, index + 1, num,
reducedNum - k);
}
}
/* Function to find out all
combinations of positive
numbers that add upto given
number. It uses findCombinationsUtil() */
function findCombinations(n)
{
// array to store the combinations
// It can contain max n elements
let arr = [];
// find all combinations
findCombinationsUtil(arr, 0, n, n);
}
// Driver Code
let n = 5;
findCombinations(n);
</script>
Producción :
1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 1 4 2 3 5
Ejercicio: Modifique la solución anterior para considerar solo elementos distintos en una combinación.
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA