Imprime combinaciones de números distintos que se suman para dar la suma N

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 

 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *