Problema de suma de subconjuntos en el espacio O (suma)

Dada una array de enteros no negativos y un valor de suma, determine si hay un subconjunto del conjunto dado con una suma igual a la suma dada.

Ejemplos: 

Input : arr[] = {4, 1, 10, 12, 5, 2}, 
          sum = 9
Output : TRUE
{4, 5} is a subset with sum 9.

Input : arr[] = {1, 8, 2, 5}, 
          sum = 4
Output : FALSE 
There exists no subset with sum 4.

Hemos discutido una solución basada en  programación dinámica en la publicación a continuación.
Programación Dinámica | Conjunto 25 (Problema de suma de subconjuntos)
La solución discutida anteriormente requiere espacio O (n * suma) y tiempo O (n * suma). Podemos optimizar el espacio. Creamos un subconjunto de array 2D booleano [2] [suma + 1]. Usando la forma de abajo hacia arriba podemos llenar esta tabla. La idea detrás de usar 2 en «subconjunto [2] [suma + 1]» es que para llenar una fila solo se requieren los valores de la fila anterior. Por lo tanto, se utilizan filas alternas haciendo que la primera sea la actual y la segunda la anterior o la primera la anterior y la segunda la actual. 

C++

// Returns true if there exists a subset
// with given sum in arr[]
#include <iostream>
using namespace std;
 
bool isSubsetSum(int arr[], int n, int sum)
{
   
    // The value of subset[i%2][j] will be true
    // if there exists a subset of sum j in
    // arr[0, 1, ...., i-1]
    bool subset[2][sum + 1];
 
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
 
            // A subset with sum 0 is always possible
            if (j == 0)
                subset[i % 2][j] = true;
 
            // If there exists no element no sum
            // is possible
            else if (i == 0)
                subset[i % 2][j] = false;
            else if (arr[i - 1] <= j)
                subset[i % 2][j] = subset[(i + 1) % 2]
             [j - arr[i - 1]] || subset[(i + 1) % 2][j];
            else
                subset[i % 2][j] = subset[(i + 1) % 2][j];
        }
    }
 
    return subset[n % 2][sum];
}
 
// Driver code
int main()
{
    int arr[] = { 6, 2, 5 };
    int sum = 7;
    int n = sizeof(arr) / sizeof(arr[0]);
    if (isSubsetSum(arr, n, sum) == true)
        cout <<"There exists a subset with given sum";
    else
        cout <<"No subset exists with given sum";
    return 0;
}
 
// This code is contributed by shivanisinghss2110

C

// Returns true if there exists a subset
// with given sum in arr[]
#include <stdio.h>
#include <stdbool.h>
 
bool isSubsetSum(int arr[], int n, int sum)
{
    // The value of subset[i%2][j] will be true
    // if there exists a subset of sum j in
    // arr[0, 1, ...., i-1]
    bool subset[2][sum + 1];
 
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
 
            // A subset with sum 0 is always possible
            if (j == 0)
                subset[i % 2][j] = true;
 
            // If there exists no element no sum
            // is possible
            else if (i == 0)
                subset[i % 2][j] = false;
            else if (arr[i - 1] <= j)
                subset[i % 2][j] = subset[(i + 1) % 2]
             [j - arr[i - 1]] || subset[(i + 1) % 2][j];
            else
                subset[i % 2][j] = subset[(i + 1) % 2][j];
        }
    }
 
    return subset[n % 2][sum];
}
 
// Driver code
int main()
{
    int arr[] = { 6, 2, 5 };
    int sum = 7;
    int n = sizeof(arr) / sizeof(arr[0]);
    if (isSubsetSum(arr, n, sum) == true)
        printf("There exists a subset with given sum");
    else
        printf("No subset exists with given sum");
    return 0;
}

Java

// Java Program to get a subset with a
// with a sum provided by the user
public class Subset_sum {
     
    // Returns true if there exists a subset
    // with given sum in arr[]
    static boolean isSubsetSum(int arr[], int n, int sum)
    {
        // The value of subset[i%2][j] will be true
        // if there exists a subset of sum j in
        // arr[0, 1, ...., i-1]
        boolean subset[][] = new boolean[2][sum + 1];
      
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
      
                // A subset with sum 0 is always possible
                if (j == 0)
                    subset[i % 2][j] = true;
      
                // If there exists no element no sum
                // is possible
                else if (i == 0)
                    subset[i % 2][j] = false;
                else if (arr[i - 1] <= j)
                    subset[i % 2][j] = subset[(i + 1) % 2]
                 [j - arr[i - 1]] || subset[(i + 1) % 2][j];
                else
                    subset[i % 2][j] = subset[(i + 1) % 2][j];
            }
        }
      
        return subset[n % 2][sum];
    }
      
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 5 };
        int sum = 7;
        int n = arr.length;
        if (isSubsetSum(arr, n, sum) == true)
            System.out.println("There exists a subset with" +
                                              "given sum");
        else
            System.out.println("No subset exists with" +
                                           "given sum");
    }
}
// This code is contributed by Sumit Ghosh

Python

# Returns true if there exists a subset
# with given sum in arr[]
 
def isSubsetSum(arr, n, sum):
    
    # The value of subset[i%2][j] will be true
    # if there exists a subset of sum j in
    # arr[0, 1, ...., i-1]
    subset = [ [False for j in range(sum + 1)] for i in range(3) ]
  
    for i in range(n + 1):
        for j in range(sum + 1):
            # A subset with sum 0 is always possible
            if (j == 0):
                subset[i % 2][j] = True
  
            # If there exists no element no sum
            # is possible
            else if (i == 0):
                subset[i % 2][j] = False
            else if (arr[i - 1] <= j):
                subset[i % 2][j] = subset[(i + 1) % 2][j - arr[i - 1]] or subset[(i + 1)
                                                                               % 2][j]
            else:
                subset[i % 2][j] = subset[(i + 1) % 2][j]
                 
    return subset[n % 2][sum]
  
# Driver code
arr = [ 6, 2, 5 ]
sum = 7
n = len(arr)
if (isSubsetSum(arr, n, sum) == True):
    print ("There exists a subset with given sum")
else:
    print ("No subset exists with given sum")
     
# This code is contributed by Sachin Bisht

C#

// C# Program to get a subset with a
// with a sum provided by the user
 
using System;
 
public class Subset_sum {
     
    // Returns true if there exists a subset
    // with given sum in arr[]
    static bool isSubsetSum(int []arr, int n, int sum)
    {
        // The value of subset[i%2][j] will be true
        // if there exists a subset of sum j in
        // arr[0, 1, ...., i-1]
        bool [,]subset = new bool[2,sum + 1];
     
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
     
                // A subset with sum 0 is always possible
                if (j == 0)
                    subset[i % 2,j] = true;
     
                // If there exists no element no sum
                // is possible
                else if (i == 0)
                    subset[i % 2,j] = false;
                else if (arr[i - 1] <= j)
                    subset[i % 2,j] = subset[(i + 1) % 2,j - arr[i - 1]] || subset[(i + 1) % 2,j];
                else
                    subset[i % 2,j] = subset[(i + 1) % 2,j];
            }
        }
     
        return subset[n % 2,sum];
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { 1, 2, 5 };
        int sum = 7;
        int n = arr.Length;
        if (isSubsetSum(arr, n, sum) == true)
            Console.WriteLine("There exists a subset with" +
                                         "given sum");
        else
            Console.WriteLine("No subset exists with" +
                                        "given sum");
    }
}
// This code is contributed by Ryuga

PHP

<?php
// Returns true if there exists a subset
// with given sum in arr[]
 
function isSubsetSum($arr, $n, $sum)
{
    // The value of subset[i%2][j] will be
    // true if there exists a subset of
    // sum j in arr[0, 1, ...., i-1]
    $subset[2][$sum + 1] = array();
 
    for ($i = 0; $i <= $n; $i++)
    {
        for ($j = 0; $j <= $sum; $j++)
        {
 
            // A subset with sum 0 is
            // always possible
            if ($j == 0)
                $subset[$i % 2][$j] = true;
 
            // If there exists no element no
            // sum is possible
            else if ($i == 0)
                $subset[$i % 2][$j] = false;
            else if ($arr[$i - 1] <= $j)
                $subset[$i % 2][$j] = $subset[($i + 1) % 2]
                                             [$j - $arr[$i - 1]] ||
                                      $subset[($i + 1) % 2][$j];
            else
                $subset[$i % 2][$j] = $subset[($i + 1) % 2][$j];
        }
    }
 
    return $subset[$n % 2][$sum];
}
 
// Driver code
$arr = array( 6, 2, 5 );
$sum = 7;
$n = sizeof($arr);
if (isSubsetSum($arr, $n, $sum) == true)
    echo ("There exists a subset with given sum");
else
    echo ("No subset exists with given sum");
 
// This code is contributed by Sach_Code
?>

Javascript

<script>
 
// Javascript Program to get a subset with a
// with a sum provided by the user
 
    // Returns true if there exists a subset
    // with given sum in arr[]
    function isSubsetSum(arr, n, sum)
    {
        // The value of subset[i%2][j] will be true
        // if there exists a subset of sum j in
        // arr[0, 1, ...., i-1]
        let subset = new Array(2);
         
        // Loop to create 2D array using 1D array
        for (var i = 0; i < subset.length; i++) {
            subset[i] = new Array(2);
        }
        
        for (let i = 0; i <= n; i++) {
            for (let j = 0; j <= sum; j++) {
        
                // A subset with sum 0 is always possible
                if (j == 0)
                    subset[i % 2][j] = true;
        
                // If there exists no element no sum
                // is possible
                else if (i == 0)
                    subset[i % 2][j] = false;
                else if (arr[i - 1] <= j)
                    subset[i % 2][j] = subset[(i + 1) % 2]
                 [j - arr[i - 1]] || subset[(i + 1) % 2][j];
                else
                    subset[i % 2][j] = subset[(i + 1) % 2][j];
            }
        }
        
        return subset[n % 2][sum];
    }
 
// driver program
        let arr = [ 1, 2, 5 ];
        let sum = 7;
        let n = arr.length;
        if (isSubsetSum(arr, n, sum) == true)
            document.write("There exists a subset with" +
                                              "given sum");
        else
            document.write("No subset exists with" +
                                           "given sum");
 
// This code is contributed by code_hunt.
</script>
Producción

There exists a subset with given sum

Otro enfoque: para reducir aún más la complejidad del espacio, creamos un subconjunto de array 1D booleana [sum+1]. Usando la forma de abajo hacia arriba podemos llenar esta tabla. La idea es que podemos verificar si la suma hasta la posición «i» es posible, entonces si el elemento actual en la array en la posición j es x, entonces la suma i+x también es posible. Atravesamos la array de suma de atrás hacia adelante para no contar ningún elemento dos veces. 

Aquí está el código para el enfoque dado:

C++

#include <iostream>
using namespace std;
 
bool isPossible(int elements[], int sum, int n)
{
    int dp[sum + 1];
     
    // Initializing with 1 as sum 0 is
    // always possible
    dp[0] = 1;
     
    // Loop to go through every element of
    // the elements array
    for(int i = 0; i < n; i++)
    {
         
        // To change the values of all possible sum
        // values to 1
        for(int j = sum; j >= elements[i]; j--)
        {
            if (dp[j - elements[i]] == 1)
                dp[j] = 1;
        }
    }
     
    // If sum is possible then return 1
    if (dp[sum] == 1)
        return true;
         
    return false;
}
 
// Driver code
int main()
{
    int elements[] = { 6, 2, 5 };
    int n = sizeof(elements) / sizeof(elements[0]);
    int sum = 7;
     
    if (isPossible(elements, sum, n))
        cout << ("YES");
    else
        cout << ("NO");
 
    return 0;
}
 
// This code is contributed by Potta Lokesh

Java

import java.io.*;
import java.util.*;
class GFG {
    static boolean isPossible(int elements[], int sum)
    {
        int dp[] = new int[sum + 1];
        // initializing with 1 as sum 0 is always possible
        dp[0] = 1;
        // loop to go through every element of the elements
        // array
        for (int i = 0; i < elements.length; i++) {
            // to change the values of all possible sum
            // values to 1
            for (int j = sum; j >= elements[i]; j--) {
                if (dp[j - elements[i]] == 1)
                    dp[j] = 1;
            }
        }
        // if sum is possible then return 1
        if (dp[sum] == 1)
            return true;
        return false;
    }
    public static void main(String[] args) throws Exception
    {
        int elements[] = { 6, 2, 5 };
        int sum = 7;
        if (isPossible(elements, sum))
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

Python3

def isPossible(elements, target):
 
    dp = [False]*(target+1)
 
    # initializing with 1 as sum 0 is always possible
    dp[0] = True
 
    # loop to go through every element of the elements array
    for ele in elements:
       
        # to change the value o all possible sum values to True
        for j in range(target, ele - 1, -1):
            if dp[j - ele]:
                dp[j] = True
 
    # If target is possible return True else False
    return dp[target]
 
# Driver code
arr = [6, 2, 5]
target = 7
 
if isPossible(arr, target):
    print("YES")
else:
    print("NO")
 
# The code is contributed by Arpan.

C#

using System;
 
class GFG {
    static Boolean isPossible(int []elements, int sum)
    {
        int []dp = new int[sum + 1];
       
        // initializing with 1 as sum 0 is always possible
        dp[0] = 1;
       
        // loop to go through every element of the elements
        // array
        for (int i = 0; i < elements.Length; i++)
        {
           
            // to change the values of all possible sum
            // values to 1
            for (int j = sum; j >= elements[i]; j--) {
                if (dp[j - elements[i]] == 1)
                    dp[j] = 1;
            }
        }
       
        // if sum is possible then return 1
        if (dp[sum] == 1)
            return true;
        return false;
    }
   
  // Driver code
    public static void Main(String[] args)
    {
        int []elements = { 6, 2, 5 };
        int sum = 7;
        if (isPossible(elements, sum))
            Console.Write("YES");
        else
            Console.Write("NO");
    }
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
function isPossible(elements, sum)
    {
        var dp =  [sum + 1];
         
        // initializing with 1 as sum 0 is always possible
        dp[0] = 1;
         
        // loop to go through every element of the elements
        // array
        for (var i = 0; i < elements.length; i++)
        {
         
            // to change the values of all possible sum
            // values to 1
            for (var j = sum; j >= elements[i]; j--) {
                if (dp[j - elements[i]] == 1)
                    dp[j] = 1;
            }
        }
         
        // if sum is possible then return 1
        if (dp[sum] == 1)
            return true;
        return false;
    }
        var elements = [ 6, 2, 5 ];
        var sum = 7;
        if (isPossible(elements, sum))
            document.write("YES");
        else
            document.write("NO");
             
// This code is contributed by shivanisinghss2110
</script>
Producción

YES

Complejidad de tiempo: O(N*K) donde N es el número de elementos en la array y K es la suma total.
Complejidad espacial: O(K), ya que se ha tomado K espacio extra.

Este artículo es una contribución de Neelesh (Neelesh_Sinha) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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

Deja una respuesta

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