Dada una array de N elementos y un entero K, imprima todos los enteros distintos que se pueden formar eligiendo K números de los N números dados. Un número de una array se puede elegir cualquier número de veces.
Ejemplos:
Entrada: k = 2, a[] = {3, 8, 17, 5}
Salida: Los 10 enteros distintos son:
6 8 10 11 13 16 20 22 25 34
Los 2 elementos elegidos son:
3+3 = 6, 5 +3 = 8, 5+5 = 10, 8+3 = 11, 8+5 = 13
8+8 = 16, 17+3 = 20, 17+5 = 22, 17+8 = 25, 17+17 = 34.Entrada: k = 3, a[] = {3, 8, 17}
Salida: Los 10 enteros distintos son:
9 14 19 23 24 28 33 37 42 51
Planteamiento: El problema se resolverá mediante recursividad. Todas las combinaciones son para probar, cuando el conteo de elementos seleccionados es igual a k, entonces mantenemos el num formado en el conjunto para que los elementos repetitivos no se cuenten dos veces. La función generateNumber(int count, int a[], int n, int num, int k) es una función recursiva, en la que el caso base es cuando el recuento se convierte en K, lo que significa que se han elegido K elementos de la array. num en el parámetro significa el número formado por número de números. En la función, itere sobre la array y para cada elemento, llame a la función recursiva con cuenta como cuenta+1 y num como num+a[i].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all distinct
// integers that can be formed by K numbers
// from a given array of N numbers.
#include <bits/stdc++.h>
using namespace std;
// stores all the distinct integers formed
set<int> s;
// Function to generate all possible numbers
void generateNumber(int count, int a[], int n,
int num, int k)
{
// Base case when K elements
// are chosen
if (k == count) {
// insert it in set
s.insert(num);
return;
}
// Choose every element and call the function
for (int i = 0; i < n; i++) {
generateNumber(count + 1, a, n, num + a[i], k);
}
}
// Function to print the distinct integers
void printDistinctIntegers(int k, int a[], int n)
{
generateNumber(0, a, n, 0, k);
cout << "The " << s.size()
<< " distinct integers are:\n";
// prints all the elements in the set
while (!s.empty()) {
cout << *s.begin() << " ";
// erase the number after printing it
s.erase(*s.begin());
}
}
// Driver Code
int main()
{
int a[] = { 3, 8, 17, 5 };
int n = sizeof(a) / sizeof(a[0]);
int k = 2;
// Calling Function
printDistinctIntegers(k, a, n);
return 0;
}
Java
// Java program to print all
// distinct integers that can
// be formed by K numbers from
// a given array of N numbers.
import java.util.*;
import java.lang.*;
class GFG
{
// stores all the distinct
// integers formed
static TreeSet<Integer> set =
new TreeSet<Integer>();
// Function to generate
// all possible numbers
public static void generateNumber(int count, int a[],
int n, int num, int k)
{
// Base case when K
// elements are chosen
if(count == k)
{
set.add(num);
return;
}
// Choose every element
// and call the function
for(int i = 0; i < n; i++)
generateNumber(count + 1, a, n,
num + a[i], k);
}
// Function to print
// the distinct integers
public static void printDistinctIntegers(int k,
int a[], int n)
{
generateNumber(0, a, n, 0, k);
System.out.print("The" + " " + set.size() +
" " + "distinct integers are: ");
System.out.println();
Iterator<Integer> i = set.iterator();
// prints all the
// elements in the set
while(set.isEmpty() == false)
{
while(i.hasNext())
{
System.out.print(i.next() + " ");
//set.remove(i.next());
}
}
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {3, 8, 17, 5};
int n = arr.length;
int k = 2;
// Calling Function
printDistinctIntegers(k, arr, n);
}
}
Python3
# Python3 program to print all distinct
# integers that can be formed by K numbers
# from a given array of N numbers.
# stores all the distinct integers formed
s = set()
# Function to generate all possible numbers
def generateNumber(count, a, n, num, k):
# Base case when K elements are chosen
if k == count:
# insert it in set
s.add(num)
return
# Choose every element and call the function
for i in range(0, n):
generateNumber(count + 1, a, n,
num + a[i], k)
# Function to print the distinct integers
def printDistinctIntegers(k, a, n):
generateNumber(0, a, n, 0, k)
print("The", len(s),
"distinct integers are:")
# prints all the elements in the set
for i in sorted(s):
print(i, end = " ")
# Driver Code
if __name__ == "__main__":
a = [3, 8, 17, 5]
n, k = len(a), 2
# Calling Function
printDistinctIntegers(k, a, n)
# This code is contributed by Rituraj Jain
C#
// C# program to print all
// distinct integers that can
// be formed by K numbers from
// a given array of N numbers.
using System;
using System.Collections.Generic;
class GFG
{
// stores all the distinct
// integers formed
static SortedSet<int> set =
new SortedSet<int>();
// Function to generate
// all possible numbers
public static void generateNumber(int count, int []a,
int n, int num, int k)
{
// Base case when K
// elements are chosen
if(count == k)
{
set.Add(num);
return;
}
// Choose every element
// and call the function
for(int i = 0; i < n; i++)
generateNumber(count + 1, a, n,
num + a[i], k);
}
// Function to print
// the distinct integers
public static void printDistinctIntegers(int k,
int []a, int n)
{
generateNumber(0, a, n, 0, k);
Console.Write("The" + " " + set.Count +
" " + "distinct integers are: ");
Console.WriteLine();
// prints all the
// elements in the set
foreach(int sets in set)
{
Console.Write(sets + " ");
}
}
// Driver Code
public static void Main (String[] args)
{
int []arr = {3, 8, 17, 5};
int n = arr.Length;
int k = 2;
// Calling Function
printDistinctIntegers(k, arr, n);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to print all distinct
// integers that can be formed by K numbers
// from a given array of N numbers.
// stores all the distinct integers formed
var s = new Set();
// Function to generate all possible numbers
function generateNumber(count, a, n, num, k)
{
// Base case when K elements
// are chosen
if (k == count)
{
// Insert it in set
s.add(num);
return;
}
// Choose every element and call the function
for(var i = 0; i < n; i++)
{
generateNumber(count + 1, a, n,
num + a[i], k);
}
}
// Function to print the distinct integers
function printDistinctIntegers(k, a, n)
{
generateNumber(0, a, n, 0, k);
document.write("The " + s.size +
" distinct integers are:<br>");
// prints all the elements in the set
while (s.size != 0)
{
var tmp = [...s].sort((a, b) => a - b)[0]
document.write(tmp + " ");
// Erase the number after printing it
s.delete(tmp);
}
}
// Driver Code
var a = [ 3, 8, 17, 5 ];
var n = a.length;
var k = 2;
// Calling Function
printDistinctIntegers(k, a, n);
// This code is contributed by itsok
</script>
Producción:
The 10 distinct integers are: 6 8 10 11 13 16 20 22 25 34