Suma de todos los subconjuntos cuya suma es un número perfecto de una array dada

Dada una array arr[] que consta de N enteros, la tarea es encontrar la suma de todos los subconjuntos de una array , cuya suma es un Número perfecto .

Ejemplos:

Entrada: arr[] = {5, 4, 6}
Salida: 6
Explicación:
Todos los subconjuntos posibles de la array arr[] son:
{5} → Sum = 5
{4} → Sum = 4.
{6} → Sum = 6.
{5, 4} → Suma = 9.
{5, 6} → Suma = 11.
{4, 6} → Suma = 10.
{5, 4, 6} → Suma = 15.
De todas las sumas de subconjuntos, se encuentra que solo 6 sumas son 2` un número perfecto.

Entrada: arr[] = {28, 6, 23, 3, 3}
Salida: 28 6 6

Enfoque recursivo : la idea es generar todos los subconjuntos posibles a partir de la array dada e imprimir la suma de esos subconjuntos cuya suma es un número perfecto .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check is a given number
// is a  perfect number or not
int isPerfect(int x)
{
    // Stores the sum of its divisors
    int sum_div = 1;
 
    // Add all divisors of x to sum_div
    for (int i = 2; i <= x / 2; ++i) {
        if (x % i == 0) {
            sum_div += i;
        }
    }
 
    // If the sum of divisors is equal
    // to the given number, return true
    if (sum_div == x) {
        return 1;
    }
 
    // Otherwise, return false
    else
        return 0;
}
 
// Function to find sum of all
// subsets from an array whose
// sum is a perfect number
void subsetSum(int arr[], int l,
               int r, int sum = 0)
{
    // Print the current subset sum
    // if it is a perfect number
    if (l > r) {
 
        // Check if sum is a
        // perfect number or not
        if (isPerfect(sum)) {
            cout << sum << " ";
        }
        return;
    }
 
    // Calculate sum of the subset
    // including arr[l]
    subsetSum(arr, l + 1, r, sum + arr[l]);
 
    // Calculate sum of the subset
    // excluding arr[l]
    subsetSum(arr, l + 1, r, sum);
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 4, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
    subsetSum(arr, 0, N - 1);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to check is a given number
// is a  perfect number or not
static int isPerfect(int x)
{
     
    // Stores the sum of its divisors
    int sum_div = 1;
   
    // Add all divisors of x to sum_div
    for(int i = 2; i <= x / 2; ++i)
    {
        if (x % i == 0)
        {
            sum_div += i;
        }
    }
   
    // If the sum of divisors is equal
    // to the given number, return true
    if (sum_div == x)
    {
        return 1;
    }
     
    // Otherwise, return false
    else
        return 0;
}
 
// Function to find sum of all
// subsets from an array whose
// sum is a perfect number
static void subsetSum(int[] arr, int l,
                      int r, int sum)
{
     
    // Print the current subset sum
    // if it is a perfect number
    if (l > r)
    {
         
        // Check if sum is a
        // perfect number or not
        if (isPerfect(sum) != 0)
        {
            System.out.print(sum + " ");
        }
        return;
    }
   
    // Calculate sum of the subset
    // including arr[l]
    subsetSum(arr, l + 1, r, sum + arr[l]);
   
    // Calculate sum of the subset
    // excluding arr[l]
    subsetSum(arr, l + 1, r, sum);
}
 
// Driver code
public static void main(String[] args)
{
    int[] arr = { 5, 4, 6 };
    int N = arr.length;
     
    subsetSum(arr, 0, N - 1, 0);
}
}
 
// This code is contributed by code_hunt

Python3

# Python3 program for the above approach
import math
 
# Function to check is a given number
# is a  perfect number or not
def isPerfect(x) :
     
    # Stores the sum of its divisors
    sum_div = 1
 
    # Add all divisors of x to sum_div
    for i in range(2, (x // 2) + 1) :
        if (x % i == 0) :
            sum_div += i
         
    # If the sum of divisors is equal
    # to the given number, return true
    if (sum_div == x) :
        return 1
     
    # Otherwise, return false
    else :
        return 0
 
# Function to find sum of all
# subsets from an array whose
# sum is a perfect number
def subsetSum(arr, l,
               r, sum) :
   
    # Print current subset sum
    # if it is a perfect number
    if (l > r) :
 
        # Check if sum is a
        # perfect number or not
        if (isPerfect(sum) != 0) :
            print(sum, end = " ")
         
        return
     
    # Calculate sum of the subset
    # including arr[l]
    subsetSum(arr, l + 1, r, sum + arr[l])
 
    # Calculate sum of the subset
    # excluding arr[l]
    subsetSum(arr, l + 1, r, sum)
 
# Driver Code
arr = [ 5, 4, 6 ]
N = len(arr)
subsetSum(arr, 0, N - 1, 0)
 
# This code is contributed by sanjoy_62.

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to check is a given number
// is a  perfect number or not
static int isPerfect(int x)
{
     
    // Stores the sum of its divisors
    int sum_div = 1;
   
    // Add all divisors of x to sum_div
    for(int i = 2; i <= x / 2; ++i)
    {
        if (x % i == 0)
        {
            sum_div += i;
        }
    }
   
    // If the sum of divisors is equal
    // to the given number, return true
    if (sum_div == x)
    {
        return 1;
    }
   
    // Otherwise, return false
    else
        return 0;
}
 
// Function to find sum of all
// subsets from an array whose
// sum is a perfect number
static void subsetSum(int[] arr, int l,
                      int r, int sum = 0)
{
     
    // Print the current subset sum
    // if it is a perfect number
    if (l > r)
    {
         
        // Check if sum is a
        // perfect number or not
        if (isPerfect(sum) != 0)
        {
            Console.Write(sum + " ");
        }
        return;
    }
   
    // Calculate sum of the subset
    // including arr[l]
    subsetSum(arr, l + 1, r, sum + arr[l]);
   
    // Calculate sum of the subset
    // excluding arr[l]
    subsetSum(arr, l + 1, r, sum);
}
 
// Driver code
static void Main()
{
    int[] arr = { 5, 4, 6 };
    int N = arr.Length;
    subsetSum(arr, 0, N - 1);
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
// javascript program for the above approach   
// Function to check is a given number
    // is a perfect number or not
    function isPerfect(x) {
 
        // Stores the sum of its divisors
        var sum_div = 1;
 
        // Add all divisors of x to sum_div
        for (i = 2; i <= x / 2; ++i) {
            if (x % i == 0) {
                sum_div += i;
            }
        }
 
        // If the sum of divisors is equal
        // to the given number, return true
        if (sum_div == x) {
            return 1;
        }
 
        // Otherwise, return false
        else
            return 0;
    }
 
    // Function to find sum of all
    // subsets from an array whose
    // sum is a perfect number
    function subsetSum(arr , l , r , sum) {
 
        // Print the current subset sum
        // if it is a perfect number
        if (l > r) {
 
            // Check if sum is a
            // perfect number or not
            if (isPerfect(sum) != 0) {
                document.write(sum + " ");
            }
            return;
        }
 
        // Calculate sum of the subset
        // including arr[l]
        subsetSum(arr, l + 1, r, sum + arr[l]);
 
        // Calculate sum of the subset
        // excluding arr[l]
        subsetSum(arr, l + 1, r, sum);
    }
 
    // Driver code
     
        var arr = [ 5, 4, 6 ];
        var N = arr.length;
 
        subsetSum(arr, 0, N - 1, 0);
 
// This code contributed by gauravrajput1
</script>
Producción: 

6

 

Complejidad de Tiempo: O(M * 2 N ), donde M es la suma de los elementos del arreglo arr[] Espacio Auxiliar: O(1)

Enfoque iterativo: dado que hay 2 N subconjuntos posibles de una array de tamaño N , la idea es iterar un bucle de 0 a 2 N – 1 y, para cada número, seleccionar todos los elementos de la array que correspondan a 1 s en la representación binaria de el número actual y luego verifique si la suma de los elementos elegidos es un número perfecto o no . Siga los pasos a continuación para resolver el problema: 

  • Iterar en el rango [0, 2 N – 1] usando la variable i y realizar los siguientes pasos:
    • Inicialice una variable, digamos S con 0 para almacenar la suma del subconjunto actual.
    • Recorra el arreglo arr[] usando la variable j y realice los siguientes pasos:
    • Compruebe si S es un número perfecto o no, si es cierto , imprima el valor de S como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check is a given
// number is a perfect number or not
int isPerfect(int x)
{
    // Stores sum of divisors
    int sum_div = 1;
 
    // Add all divisors of x to sum_div
    for (int i = 2; i <= x / 2; ++i) {
        if (x % i == 0) {
            sum_div += i;
        }
    }
 
    // If the sum of divisors is equal
    // to the given number, return true
    if (sum_div == x) {
        return 1;
    }
 
    // Otherwise, return false
    else
        return 0;
}
 
// Function to find the sum of all the
// subsets from an array whose sum is
// a perfect number
void subsetSum(int arr[], int n)
{
    // Stores the total number of
    // subsets, i.e. 2 ^ n
    long long total = 1 << n;
 
    // Consider all numbers from 0 to 2 ^ n - 1
    for (long long i = 0; i < total; i++) {
        long long sum = 0;
 
        // Consider array elements from
        // positions of set bits in the
        // binary representation of n
        for (int j = 0; j < n; j++)
            if (i & (1 << j))
                sum += arr[j];
 
        // If sum of chosen elements
        // is a perfect number
        if (isPerfect(sum)) {
            cout << sum << " ";
        }
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 4, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
    subsetSum(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
  // Function to check is a given
  // number is a perfect number or not
  static int isPerfect(int x)
  {
     
    // Stores sum of divisors
    int sum_div = 1;
 
    // Add all divisors of x to sum_div
    for (int i = 2; i <= x / 2; ++i) {
      if (x % i == 0) {
        sum_div += i;
      }
    }
 
    // If the sum of divisors is equal
    // to the given number, return true
    if (sum_div == x) {
      return 1;
    }
 
    // Otherwise, return false
    else
      return 0;
  }
 
  // Function to find the sum of all the
  // subsets from an array whose sum is
  // a perfect number
  static void subsetSum(int arr[], int n)
  {
     
    // Stores the total number of
    // subsets, i.e. 2 ^ n
    long total = 1 << n;
 
    // Consider all numbers from 0 to 2 ^ n - 1
    for (long i = 0; i < total; i++) {
      int sum = 0;
 
      // Consider array elements from
      // positions of set bits in the
      // binary representation of n
      for (int j = 0; j < n; j++)
        if ((i & (1 << j)) != 0)
          sum += arr[j];
 
      // If sum of chosen elements
      // is a perfect number
      if (isPerfect(sum) != 0) {
        System.out.print(sum + " ");
      }
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 5, 4, 6 };
    int N = arr.length;
    subsetSum(arr, N);
  }
}
 
// This code is contributed by souravghosh0416.

Python3

# Python3 program for the above approach
 
# Function to check is a given
# number is a perfect number or not
def isPerfect(x):
     
    # Stores sum of divisors
    sum_div = 1
 
    # Add all divisors of x to sum_div
    for i in range(2, int(x/2 + 1)):
        if (x % i == 0):
            sum_div = sum_div + i
 
    # If the sum of divisors is equal
    # to the given number, return true
    if (sum_div == x):
        return 1
 
    # Otherwise, return false
    else:
        return 0
 
# Function to find the sum of all the
# subsets from an array whose sum is
# a perfect number
def subsetSum(arr, n):
     
    # Stores the total number of
    # subsets, i.e. 2 ^ n
    total = 1 << n
 
    # Consider all numbers from 0 to 2 ^ n - 1
    for i in range(total):
        sum = 0
 
        # Consider array elements from
        # positions of set bits in the
        # binary representation of n
        for j in range(n):
            if (i & (1 << j) != 0):
                sum = sum + arr[j]
 
        # If sum of chosen elements
        # is a perfect number
        if (isPerfect(sum)):
            print(sum, " ")
 
# Driver Code
arr = [5, 4, 6]
N = len(arr)
 
subsetSum(arr, N)
 
# This code is contributed by Dharanendra L V.

C#

// C# program for the above approach
using System;
class GFG{
 
  // Function to check is a given
  // number is a perfect number or not
  static int isPerfect(int x)
  {
     
    // Stores sum of divisors
    int sum_div = 1;
 
    // Add all divisors of x to sum_div
    for (int i = 2; i <= x / 2; ++i) {
      if (x % i == 0) {
        sum_div += i;
      }
    }
 
    // If the sum of divisors is equal
    // to the given number, return true
    if (sum_div == x) {
      return 1;
    }
 
    // Otherwise, return false
    else
      return 0;
  }
 
  // Function to find the sum of all the
  // subsets from an array whose sum is
  // a perfect number
  static void subsetSum(int[] arr, int n)
  {
     
    // Stores the total number of
    // subsets, i.e. 2 ^ n
    long total = 1 << n;
 
    // Consider all numbers from 0 to 2 ^ n - 1
    for (long i = 0; i < total; i++) {
      int sum = 0;
 
      // Consider array elements from
      // positions of set bits in the
      // binary representation of n
      for (int j = 0; j < n; j++)
        if ((i & (1 << j)) != 0)
          sum += arr[j];
 
      // If sum of chosen elements
      // is a perfect number
      if (isPerfect(sum) != 0) {
        Console.Write(sum + " ");
      }
    }
  }
 
// Driver Code
static public void Main()
{
    int[] arr = { 5, 4, 6 };
    int N = arr.Length;
    subsetSum(arr, N);
}
}
 
// This code is contributed by splevel62.

Javascript

<script>
// javascript program for the above approach
 
 // Function to check is a given
  // number is a perfect number or not
  function isPerfect(x)
  {
     
    // Stores sum of divisors
    var sum_div = 1;
 
    // Add all divisors of x to sum_div
    for (var i = 2; i <= parseInt(x / 2); ++i) {
      if (x % i == 0) {
        sum_div += i;
      }
    }
 
    // If the sum of divisors is equal
    // to the given number, return true
    if (sum_div == x) {
      return 1;
    }
 
    // Otherwise, return false
    else
      return 0;
  }
 
  // Function to find the sum of all the
  // subsets from an array whose sum is
  // a perfect number
  function subsetSum(arr , n)
  {
     
    // Stores the total number of
    // subsets, i.e. 2 ^ n
    var total = 1 << n;
 
    // Consider all numbers from 0 to 2 ^ n - 1
    for (i = 0; i < total; i++) {
      var sum = 0;
 
      // Consider array elements from
      // positions of set bits in the
      // binary representation of n
      for (j = 0; j < n; j++)
        if ((i & (1 << j)) != 0)
          sum += arr[j];
 
      // If sum of chosen elements
      // is a perfect number
      if (isPerfect(sum) != 0) {
        document.write(sum + " ");
      }
    }
  }
 
  // Driver Code
  var arr = [ 5, 4, 6 ];
  var N = arr.length;
  subsetSum(arr, N);
 
// This code is contributed by 29AjayKumar
</script>
Producción: 

6

 

Complejidad de tiempo: O((N + M) * 2 N ), donde M es la suma de los elementos del arreglo , arr[]
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por patelajeet 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 *