Dado un entero positivo N , la tarea es encontrar todas las combinaciones de enteros positivos que suman el entero N dado . El programa debe imprimir solo combinaciones, no permutaciones y todos los enteros en una combinación deben ser distintos. Por ejemplo, para la entrada 3, se debe imprimir 1, 2 o 2, 1 y no se debe imprimir 1, 1, 1 ya que los números enteros no son distintos.
Ejemplos:
Entrada: N = 3
Salida:
1 2
3
Entrada: N = 7
Salida:
1 2 4
1 6
2 5
3 4
7
Enfoque: El enfoque es una extensión del enfoque discutido aquí . La idea utilizada para obtener todos los elementos distintos es que primero encontramos todos los elementos que se suman para dar la suma N . Luego iteramos sobre cada uno de los elementos y almacenamos los elementos en el conjunto . Almacenar los elementos en el conjunto eliminaría todos los elementos duplicados, y luego sumamos la suma de los elementos del conjunto y verificamos si es igual a N o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
/* arr[] to store all the distinct elements
index - next location in array
num - given number
reducedNum - reduced number */
void findCombinationsUtil(int arr[], int index,
int n, int red_num)
{
// Set to store all the
// distinct elements
set<int> s;
int sum = 0;
// Base condition
if (red_num < 0) {
return;
}
if (red_num == 0) {
// Iterate over all the elements
// and store it into the set
for (int i = 0; i < index; i++) {
s.insert(arr[i]);
}
// Calculate the sum of all
// the elements of the set
for (auto itr = s.begin();
itr != s.end(); itr++) {
sum = sum + (*itr);
}
// Compare whether the sum is equal to n or not,
// if it is equal to n print the numbers
if (sum == n) {
for (auto i = s.begin();
i != s.end(); i++) {
cout << *i << " ";
}
cout << endl;
return;
}
}
// Find previous number stored in the array
int prev = (index == 0) ? 1 : arr[index - 1];
for (int k = prev; k <= n; k++) {
// Store all the numbers recursively
// into the arr[]
arr[index] = k;
findCombinationsUtil(arr, index + 1,
n, red_num - k);
}
}
// Function to find all the
// distinct combinations of n
void findCombinations(int n)
{
int a[n];
findCombinationsUtil(a, 0, n, n);
}
// Driver code
int main()
{
int n = 7;
findCombinations(n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
/* arr[] to store all the distinct elements
index - next location in array
num - given number
reducedNum - reduced number */
static void findCombinationsUtil(int arr[], int index,
int n, int red_num)
{
// Set to store all the
// distinct elements
HashSet<Integer> s = new HashSet<>();
int sum = 0;
// Base condition
if (red_num < 0)
{
return;
}
if (red_num == 0)
{
// Iterate over all the elements
// and store it into the set
for (int i = 0; i < index; i++)
{
s.add(arr[i]);
}
// Calculate the sum of all
// the elements of the set
for (Integer itr : s)
{
sum = sum + itr;
}
// Compare whether the sum is equal to n or not,
// if it is equal to n print the numbers
if (sum == n)
{
for (Integer i : s)
{
System.out.print(i+" ");
}
System.out.println();
return;
}
}
// Find previous number stored in the array
int prev = (index == 0) ? 1 : arr[index - 1];
for (int k = prev; k <= n; k++)
{
// Store all the numbers recursively
// into the arr[]
if(index < n)
{
arr[index] = k;
findCombinationsUtil(arr, index + 1,
n, red_num - k);
}
}
}
// Function to find all the
// distinct combinations of n
static void findCombinations(int n)
{
int []a = new int[n];
findCombinationsUtil(a, 0, n, n);
}
// Driver code
public static void main(String arr[])
{
int n = 7;
findCombinations(n);
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach
# arr[] to store all the distinct elements
# index - next location in array
# num - given number
# reducedNum - reduced number
def findCombinationsUtil(arr, index, n, red_num):
# Set to store all the
# distinct elements
s = set()
sum = 0
# Base condition
if (red_num < 0):
return
if (red_num == 0):
# Iterate over all the elements
# and store it into the set
for i in range(index):
s.add(arr[i])
# Calculate the sum of all
# the elements of the set
for itr in s:
sum = sum + (itr)
# Compare whether the sum is equal to n or not,
# if it is equal to n print the numbers
if (sum == n):
for i in s:
print(i, end = " ")
print("\n", end = "")
return
# Find previous number stored in the array
if (index == 0):
prev = 1
else:
prev = arr[index - 1]
for k in range(prev, n + 1, 1):
# Store all the numbers recursively
# into the arr[]
arr[index] = k
findCombinationsUtil(arr, index + 1,
n, red_num - k)
# Function to find all the
# distinct combinations of n
def findCombinations(n):
a = [0 for i in range(n + 1)]
findCombinationsUtil(a, 0, n, n)
# Driver code
if __name__ == '__main__':
n = 7
findCombinations(n)
# This code is contributed by Surendra_Gangwar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
/* arr[] to store all the distinct elements
index - next location in array
num - given number
reducedNum - reduced number */
static void findCombinationsUtil(int []arr, int index,
int n, int red_num)
{
// Set to store all the
// distinct elements
HashSet<int> s = new HashSet<int>();
int sum = 0;
// Base condition
if (red_num < 0)
{
return;
}
if (red_num == 0)
{
// Iterate over all the elements
// and store it into the set
for (int i = 0; i < index; i++)
{
s.Add(arr[i]);
}
// Calculate the sum of all
// the elements of the set
foreach (int itr in s)
{
sum = sum + itr;
}
// Compare whether the sum is equal to n or not,
// if it is equal to n print the numbers
if (sum == n)
{
foreach (int i in s)
{
Console.Write(i+" ");
}
Console.WriteLine();
return;
}
}
// Find previous number stored in the array
int prev = (index == 0) ? 1 : arr[index - 1];
for (int k = prev; k <= n; k++)
{
// Store all the numbers recursively
// into the arr[]
if(index < n)
{
arr[index] = k;
findCombinationsUtil(arr, index + 1,
n, red_num - k);
}
}
}
// Function to find all the
// distinct combinations of n
static void findCombinations(int n)
{
int []a = new int[n];
findCombinationsUtil(a, 0, n, n);
}
// Driver code
public static void Main(String []arr)
{
int n = 7;
findCombinations(n);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
/* arr[] to store all the distinct elements
index - next location in array
num - given number
reducedNum - reduced number */
function findCombinationsUtil(arr, index, n, red_num) {
// Set to store all the
// distinct elements
var s = new Set();
var sum = 0;
// Base condition
if (red_num < 0) {
return;
}
if (red_num === 0) {
// Iterate over all the elements
// and store it into the set
for (var i = 0; i < index; i++) {
s.add(arr[i]);
}
// Calculate the sum of all
// the elements of the set
for (const itr of s) {
sum = sum + itr;
}
// Compare whether the sum is equal to n or not,
// if it is equal to n print the numbers
if (sum === n) {
for (const i of s) {
document.write(i + " ");
}
document.write("<br>");
return;
}
}
// Find previous number stored in the array
var prev = index === 0 ? 1 : arr[index - 1];
for (var k = prev; k <= n; k++) {
// Store all the numbers recursively
// into the arr[]
if (index < n) {
arr[index] = k;
findCombinationsUtil(arr, index + 1, n, red_num - k);
}
}
}
// Function to find all the
// distinct combinations of n
function findCombinations(n) {
var a = new Array(n).fill(0);
findCombinationsUtil(a, 0, n, n);
}
// Driver code
var n = 7;
findCombinations(n);
</script>
Producción:
1 2 4 1 6 2 5 3 4 7
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por deepak_2431 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA