Dada una array de enteros y una suma, la tarea es imprimir todos los subconjuntos de la array dada con una suma igual a una suma dada.
Ejemplos:
Input : arr[] = {2, 3, 5, 6, 8, 10}
sum = 10
Output : 5 2 3
2 8
10
Input : arr[] = {1, 2, 3, 4, 5}
sum = 10
Output : 4 3 2 1
5 3 2
5 4 1
Preguntado en Tesco
Este problema es principalmente una extensión del problema de la suma de subconjuntos . Aquí no solo necesitamos encontrar si hay un subconjunto con la suma dada, sino que también necesitamos imprimir todos los subconjuntos con una suma dada.
Al igual que en la publicación anterior , construimos una array 2D dp[][] tal que dp[i][j] almacena verdadero si la suma j es posible con elementos de array de 0 a i.
Después de llenar dp[][], lo recorremos recursivamente desde dp[n-1][sum]. Para la celda que se está atravesando, almacenamos el camino antes de llegar a ella y consideramos dos posibilidades para el elemento.
- El elemento está incluido en la ruta actual.
- El elemento no está incluido en la ruta actual.
Cada vez que la suma se convierte en 0, detenemos las llamadas recursivas e imprimimos la ruta actual. A continuación se muestra una implementación de la idea anterior.
Implementación:
C++
// C++ program to count all subsets with
// given sum.
#include <bits/stdc++.h>
using namespace std;
// dp[i][j] is going to store true if sum j is
// possible with array elements from 0 to i.
bool** dp;
void display(const vector<int>& v)
{
for (int i = 0; i < v.size(); ++i)
printf("%d ", v[i]);
printf("\n");
}
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
void printSubsetsRec(int arr[], int i, int sum, vector<int>& p)
{
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sum OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
{
p.push_back(arr[i]);
// Display Only when Sum of elements of p is equal to sum
if (arr[i] == sum)
display(p);
return;
}
// If sum becomes 0
if (i == 0 && sum == 0)
{
display(p);
return;
}
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
{
// Create a new vector to store path
vector<int> b = p;
printSubsetsRec(arr, i-1, sum, b);
}
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
{
p.push_back(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
}
}
// Prints all subsets of arr[0..n-1] with sum 0.
void printAllSubsets(int arr[], int n, int sum)
{
if (n == 0 || sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = new bool*[n];
for (int i=0; i<n; ++i)
{
dp[i] = new bool[sum + 1];
dp[i][0] = true;
}
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for (int i = 1; i < n; ++i)
for (int j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? dp[i-1][j] ||
dp[i-1][j-arr[i]]
: dp[i - 1][j];
if (dp[n-1][sum] == false)
{
printf("There are no subsets with sum %d\n", sum);
return;
}
// Now recursively traverse dp[][] to find all
// paths from dp[n-1][sum]
vector<int> p;
printSubsetsRec(arr, n-1, sum, p);
}
// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
int sum = 10;
printAllSubsets(arr, n, sum);
return 0;
}
Java
// A Java program to count all subsets with given sum.
import java.util.ArrayList;
public class SubSet_sum_problem
{
// dp[i][j] is going to store true if sum j is
// possible with array elements from 0 to i.
static boolean[][] dp;
static void display(ArrayList<Integer> v)
{
System.out.println(v);
}
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
static void printSubsetsRec(int arr[], int i, int sum,
ArrayList<Integer> p)
{
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sum OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
{
p.add(arr[i]);
display(p);
p.clear();
return;
}
// If sum becomes 0
if (i == 0 && sum == 0)
{
display(p);
p.clear();
return;
}
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
{
// Create a new vector to store path
ArrayList<Integer> b = new ArrayList<>();
b.addAll(p);
printSubsetsRec(arr, i-1, sum, b);
}
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
{
p.add(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
}
}
// Prints all subsets of arr[0..n-1] with sum 0.
static void printAllSubsets(int arr[], int n, int sum)
{
if (n == 0 || sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = new boolean[n][sum + 1];
for (int i=0; i<n; ++i)
{
dp[i][0] = true;
}
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for (int i = 1; i < n; ++i)
for (int j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? (dp[i-1][j] ||
dp[i-1][j-arr[i]])
: dp[i - 1][j];
if (dp[n-1][sum] == false)
{
System.out.println("There are no subsets with" +
" sum "+ sum);
return;
}
// Now recursively traverse dp[][] to find all
// paths from dp[n-1][sum]
ArrayList<Integer> p = new ArrayList<>();
printSubsetsRec(arr, n-1, sum, p);
}
//Driver Program to test above functions
public static void main(String args[])
{
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
int sum = 10;
printAllSubsets(arr, n, sum);
}
}
//This code is contributed by Sumit Ghosh
Python3
# A Python program to count all subsets with given sum.
# dp[i][j] is going to store True if sum j is
# possible with array elements from 0 to i.
dp = [[]]
def display(v):
print(v)
# A recursive function to print all subsets with the
# help of dp[][]. list p[] stores current subset.
def printSubsetsRec(arr, i, sum, p):
# If we reached end and sum is non-zero. We print
# p[] only if arr[0] is equal to sum OR dp[0][sum]
# is True.
if (i == 0 and sum != 0 and dp[0][sum]):
p.append(arr[i])
display(p)
p = []
return
# If sum becomes 0
if (i == 0 and sum == 0):
display(p)
p = []
return
# If given sum can be achieved after ignoring
# current element.
if (dp[i-1][sum]):
# Create a new list to store path
b = []
b.extend(p)
printSubsetsRec(arr, i-1, sum, b)
# If given sum can be achieved after considering
# current element.
if (sum >= arr[i] and dp[i-1][sum-arr[i]]):
p.append(arr[i])
printSubsetsRec(arr, i-1, sum-arr[i], p)
# Prints all subsets of arr[0..n-1] with sum 0.
def printAllSubsets(arr, n, sum):
if (n == 0 or sum < 0):
return
# Sum 0 can always be achieved with 0 elements
global dp
dp = [[False for i in range(sum+1)] for j in range(n)]
for i in range(n):
dp[i][0] = True
# Sum arr[0] can be achieved with single element
if (arr[0] <= sum):
dp[0][arr[0]] = True
# Fill rest of the entries in dp[][]
for i in range(1, n):
for j in range(0, sum + 1):
if (arr[i] <= j):
dp[i][j] = (dp[i-1][j] or dp[i-1][j-arr[i]])
else:
dp[i][j] = dp[i - 1][j]
if (dp[n-1][sum] == False):
println("There are no subsets with sum ", sum)
return
# Now recursively traverse dp[][] to find all
# paths from dp[n-1][sum]
p = []
printSubsetsRec(arr, n-1, sum, p)
arr = [1, 2, 3, 4, 5]
n = len(arr)
sum = 10
printAllSubsets(arr, n, sum)
# This code is contributed by Lovely Jain
C#
// A C# program to count all subsets with given sum.
using System;
using System.Collections.Generic;
public class SubSet_sum_problem
{
// dp[i][j] is going to store true if sum j is
// possible with array elements from 0 to i.
static bool[, ] dp;
static void display(List<int> v)
{
foreach(var i in v) Console.Write(i + " ");
Console.WriteLine();
}
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
static void printSubsetsRec(int[] arr, int i, int sum,
List<int> p)
{
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sum OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0, sum]) {
p.Add(arr[i]);
display(p);
p.Clear();
return;
}
// If sum becomes 0
if (i == 0 && sum == 0) {
display(p);
p.Clear();
return;
}
// If given sum can be achieved after ignoring
// current element.
if (dp[i - 1, sum]) {
// Create a new vector to store path
List<int> b = new List<int>();
b.AddRange(p);
printSubsetsRec(arr, i - 1, sum, b);
}
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i - 1, sum - arr[i]]) {
p.Add(arr[i]);
printSubsetsRec(arr, i - 1, sum - arr[i], p);
}
}
// Prints all subsets of arr[0..n-1] with sum 0.
static void printAllSubsets(int[] arr, int n, int sum)
{
if (n == 0 || sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = new bool[n, sum + 1];
for (int i = 0; i < n; ++i) {
dp[i, 0] = true;
}
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0, arr[0]] = true;
// Fill rest of the entries in dp[][]
for (int i = 1; i < n; ++i)
for (int j = 0; j < sum + 1; ++j)
dp[i, j] = (arr[i] <= j)
? (dp[i - 1, j]
|| dp[i - 1, j - arr[i]])
: dp[i - 1, j];
if (dp[n - 1, sum] == false) {
Console.WriteLine("There are no subsets with"
+ " sum " + sum);
return;
}
// Now recursively traverse dp[][] to find all
// paths from dp[n-1][sum]
List<int> p = new List<int>();
printSubsetsRec(arr, n - 1, sum, p);
}
// Driver Program to test above functions
public static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
int sum = 10;
printAllSubsets(arr, n, sum);
}
}
// This code is contributed by phasing17
Javascript
<script>
// A Javascript program to count all subsets with given sum.
// dp[i][j] is going to store True if sum j is
// possible with array elements from 0 to i.
var dp = [];
function display(v){
document.write(v+"<br>");
}
// A recursive function to print all subsets with the
// help of dp[][]. list p[] stores current subset.
function printSubsetsRec(arr, i, sum, p){
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sum OR dp[0][sum]
// is True.
if (i === 0 && sum !== 0 && dp[0][sum] !== 0){
p.push(arr[i]);
display(p);
p = [];
return;
}
// If sum becomes 0
if (i == 0 && sum == 0){
display(p);
p = [];
return;
}
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum]){
// Create a new list to store path
b = [...p];
printSubsetsRec(arr, i-1, sum, b);
}
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]]){
p.push(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
}
}
// Prints all subsets of arr[0..n-1] with sum 0.
function printAllSubsets(arr, n, sum){
if (n == 0 || sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
for(let i = 0; i < n; i++){
dp[i]= [];
for(let j = 0; j < sum+1; j++)
dp[i].push(false);
}
for(let i = 0; i < n; i++)
dp[i][0] = true;
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for(var i = 1; i < n; i++){
for(let j = 0; j < sum+1; j++){
if (arr[i] <= j)
dp[i][j] = (dp[i-1][j] || dp[i-1][j-arr[i]]);
else
dp[i][j] = dp[i - 1][j];
}
}
if (dp[n-1][sum] == false){
document.write("There are no subsets with sum "+ sum);
return;
}
// Now recursively traverse dp[][] to find all
// paths from dp[n-1][sum]
p = [];
printSubsetsRec(arr, n-1, sum, p);
}
arr = [1, 2, 3, 4, 5];
n = arr.length
sum = 10
printAllSubsets(arr, n, sum);
// This code is contributed by repakaeswaripriya.
</script>
Producción
4 3 2 1 5 3 2 5 4 1
Otro enfoque :
Para cada elemento de la array, primero decida tomarlo o no en el subconjunto. Defina una función que se encargará de todo esto. La función se llama una vez en la función principal. Se declaran los campos de clase estática que serán operados por nuestra función. En cada llamada, la función verifica la condición de los campos. En nuestro caso, verifica si la suma actual es igual a la suma dada y, en consecuencia, incrementa el campo de clase respectivo. Si no, realiza llamadas de función tomando todo el caso. Entonces, el número de llamadas a funciones será igual al número de casos. Así que aquí se realizan dos llamadas: una tomando el elemento en el subconjunto e incrementando la suma actual y otra no tomando el elemento.
A continuación se muestra la implementación:
C++
// C++ code to find the number of possible subset with given sum
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt;
int sum;
void f(int pat[], int i, int currSum)
{
if (currSum == sum)
{
cnt++;
return;
}
if (currSum < sum && i < n)
{
f(pat, i + 1, currSum + pat[i]);
f(pat, i + 1, currSum);
}
}
int main()
{
cnt = 0;
n = 5;
sum = 10;
int pat[] = {2, 3, 5, 6, 8, 10};
f(pat, 0, 0);
cout << cnt << endl;
return 0;
}
/*This code is contributed by Nikhil Goswami (@nikhil070g) */
Java
// Java code to find the number of
// possible subset with given sum
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
static int count;
static int sum;
static int n;
// Driver code
public static void main (String[] args) {
count = 0;
n = 5;
sum = 10;
int[] pat = {2, 3, 5, 6, 8, 10};
f(pat, 0, 0);
System.out.println(count);
}
// Function to select or not the array element
// to form a subset with given sum
static void f(int[] pat, int i, int currSum) {
if (currSum == sum) {
count++;
return;
}
if (currSum < sum && i < n) {
f(pat, i+1, currSum + pat[i]);
f(pat, i+1, currSum);
}
}
}
Python3
# Python code to find the number of # possible subset with given sum def f(pat, i, currSum): global cnt, n, sum if (currSum == sum): cnt += 1 return if (currSum < sum and i < n): f(pat, i + 1, currSum + pat[i]) f(pat, i + 1, currSum) # driver code cnt = 0 n = 5 sum = 10 pat = [2, 3, 5, 6, 8, 10] f(pat, 0, 0) print(cnt) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript code to find the number of
// possible subset with given sum
let n;
let cnt;
let sum;
function f(pat, i, currSum)
{
if (currSum == sum)
{
cnt++;
return;
}
if (currSum < sum && i < n)
{
f(pat, i + 1, currSum + pat[i]);
f(pat, i + 1, currSum);
}
}
// driver code
cnt = 0;
n = 5;
sum = 10;
let pat = [2, 3, 5, 6, 8, 10];
f(pat, 0, 0);
document.write(cnt,"</br>");
// This code is contributed by shinjanpatra
</script>
C#
// C# code to find the number of
// possible subset with given sum
using System;
class GFG {
static int count;
static int sum;
static int n;
// Driver code
public static void Main(string[] args)
{
count = 0;
n = 5;
sum = 10;
int[] pat = { 2, 3, 5, 6, 8, 10 };
f(pat, 0, 0);
Console.WriteLine(count);
}
// Function to select or not the array element
// to form a subset with given sum
static void f(int[] pat, int i, int currSum)
{
if (currSum == sum) {
count++;
return;
}
if (currSum < sum && i < n) {
f(pat, i + 1, currSum + pat[i]);
f(pat, i + 1, currSum);
}
}
}
// This code is contributed by phasing17
Producción
2
Este artículo es una contribución de Jas Kaur . 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.
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