encontrar todos los subconjuntos que sumn un valor particular

Dado un conjunto de números: {1, 3, 2, 5, 4, 9}, encuentre la cantidad de subconjuntos que sumn un valor particular (digamos, 9 para este ejemplo).

Esto es similar al problema de la sum de subconjuntos con la ligera diferencia de que, en lugar de verificar si el conjunto tiene un subconjunto que sum 9, tenemos que encontrar el número de dichos subconjuntos. Estoy siguiendo la solución para el problema de sum de subconjuntos aquí . Pero me pregunto cómo puedo modificarlo para devolver el recuento de subconjuntos.

def total_subsets_matching_sum(numbers, sum): array = [1] + [0] * (sum) for current_number in numbers: for num in xrange(sum - current_number, -1, -1): if array[num]: array[num + current_number] += array[num] return array[sum] assert(total_subsets_matching_sum(range(1, 10), 9) == 8) assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4) 

Explicación

Este es uno de los problemas clásicos. La idea es encontrar el número de sums posibles con el número actual. Y es cierto que, hay exactamente una forma de llevar la sum a 0. Al principio, tenemos solo un número. Comenzamos desde nuestro objective (variable Máxima en la solución) y restamos ese número. Si es posible obtener una sum de ese número (el elemento de la matriz correspondiente a ese número no es cero) entonces agréguelo al elemento de la matriz correspondiente al número actual. El progtwig sería más fácil de entender de esta manera

 for current_number in numbers: for num in xrange(sum, current_number - 1, -1): if array[num - current_number]: array[num] += array[num - current_number] 

Cuando el número es 1, solo hay una manera de obtener la sum de 1 (1-1 se convierte en 0 y el elemento correspondiente a 0 es 1). Entonces la matriz sería así (recuerda que el elemento cero tendrá 1)

 [1, 1, 0, 0, 0, 0, 0, 0, 0, 0] 

Ahora, el segundo número es 2. Comenzamos restando 2 de 9 y no es válido (dado que el elemento de matriz de 7 es cero, omitimos eso) seguimos haciendo esto hasta 3. Cuando su 3, 3 – 2 es 1 y el elemento de matriz correspondiente a 1 es 1 y lo agregamos al elemento de matriz de 3. y cuando su 2, 2 – 2 se convierte en 0 y nosotros el valor correspondiente a 0 en el elemento de matriz de 2. Después de esta iteración, la matriz se ve así

 [1, 1, 1, 1, 0, 0, 0, 0, 0, 0] 

Seguimos haciendo esto hasta que procesamos todos los números y la matriz después de cada iteración se ve así

 [1, 1, 0, 0, 0, 0, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 0, 0, 0, 0] [1, 1, 1, 2, 1, 1, 1, 0, 0, 0] [1, 1, 1, 2, 2, 2, 2, 2, 1, 1] [1, 1, 1, 2, 2, 3, 3, 3, 3, 3] [1, 1, 1, 2, 2, 3, 4, 4, 4, 5] [1, 1, 1, 2, 2, 3, 4, 5, 5, 6] [1, 1, 1, 2, 2, 3, 4, 5, 6, 7] [1, 1, 1, 2, 2, 3, 4, 5, 6, 8] 

Después de la última iteración, habríamos considerado todos los números y la cantidad de formas de obtener el objective sería el elemento de la matriz correspondiente al valor objective. En nuestro caso, Array [9] después de la última iteración es 8.

Puede usar la Progtwigción Dinámica. La complejidad de Algo es O (Suma * N) y usa memoria O (Suma) .

Aquí está mi implementación en C #:

 private static int GetmNumberOfSubsets(int[] numbers, int sum) { int[] dp = new int[sum + 1]; dp[0] = 1; int currentSum =0; for (int i = 0; i < numbers.Length; i++) { currentSum += numbers[i]; for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--) dp[j] += dp[j - numbers[i]]; } return dp[sum]; } 

Notas : Como el número de subconjuntos puede tener el valor 2 ^ N, es fácil que se desborde el tipo int.

Algo funciona solo para números positivos.

Aquí hay una Java Solution :

Este es un problema clásico de seguimiento de Atrás para encontrar todos los subconjuntos posibles de la matriz o conjunto de enteros que es la entrada y luego filtering aquellos que sumn un target dado

 import java.util.HashSet; import java.util.StringTokenizer; /** * Created by anirudh on 12/5/15. */ public class findSubsetsThatSumToATarget { /** * The collection for storing the unique sets that sum to a target. */ private static HashSet allSubsets = new HashSet<>(); /** * The String token */ private static final String token = " "; /** * The method for finding the subsets that sum to a target. * * @param input The input array to be processed for subset with particular sum * @param target The target sum we are looking for * @param ramp The Temporary String to be beefed up during recursive iterations(By default value an empty String) * @param index The index used to traverse the array during recursive calls */ public static void findTargetSumSubsets(int[] input, int target, String ramp, int index) { if(index > (input.length - 1)) { if(getSum(ramp) == target) { allSubsets.add(ramp); } return; } //First recursive call going ahead selecting the int at the currenct index value findTargetSumSubsets(input, target, ramp + input[index] + token, index + 1); //Second recursive call going ahead WITHOUT selecting the int at the currenct index value findTargetSumSubsets(input, target, ramp, index + 1); } /** * A helper Method for calculating the sum from a string of integers * * @param intString the string subset * @return the sum of the string subset */ private static int getSum(String intString) { int sum = 0; StringTokenizer sTokens = new StringTokenizer(intString, token); while (sTokens.hasMoreElements()) { sum += Integer.parseInt((String) sTokens.nextElement()); } return sum; } /** * Cracking it down here : ) * * @param args command line arguments. */ public static void main(String[] args) { int [] n = {24, 1, 15, 3, 4, 15, 3}; int counter = 1; FindSubsetsThatSumToATarget.findTargetSumSubsets(n, 25, "", 0); for (String str: allSubsets) { System.out.println(counter + ") " + str); counter++; } } } 

Proporciona valores separados por espacios de los subconjuntos que se sumn a un objective.

Imprimiría valores separados por comas para los subconjuntos que sumn 25 en {24, 1, 15, 3, 4, 15, 3}

1) 24 1

2) 3 4 15 3

3) 15 3 4 3

El mismo sitio geeksforgeeks también analiza la solución para generar todos los subconjuntos que sumn un valor particular: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/

En su caso, en lugar de los conjuntos de resultados, solo necesita contarlos. Asegúrese de verificar la versión optimizada en la misma página, ya que es un problema NP-completo .

Esta pregunta también se ha formulado y respondido antes en stackoverflow sin mencionar que se trata de un problema de sum de subconjuntos: encontrar todas las combinaciones posibles de números para alcanzar una sum dada

Este es mi progtwig en ruby. Devolverá matrices, cada una sosteniendo las subsecuencias sumndo al valor objective provisto.

 array = [1, 3, 4, 2, 7, 8, 9] 0..array.size.times.each do |i| @ary.combination(i).to_a.each { |a| print a if a.inject(:+) == 9} end 

He resuelto esto por java. Esta solución es bastante simple.

 import java.util.*; public class Recursion { static void sum(int[] arr, int i, int sum, int target, String s) { for(int j = i+1; j 

La solución de DP habitual es verdadera para el problema.

Una optimización que puede hacer es mantener un recuento de cuántas soluciones existen para la sum en particular en lugar de los conjuntos reales que componen esa sum …

Esta es mi implementación de progtwigción dinámica en JS. Devolverá una matriz de matrices, cada una sosteniendo las subsecuencias sumndo al valor objective provisto.

 function getSummingItems(a,t){ return a.reduce((h,n) => Object.keys(h) .reduceRight((m,k) => +k+n < = t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n))) : m[k].map(sa => sa.concat(n)),m) : m, h), {0:[[]]})[t]; } var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20] tgt = 42, res = []; console.time("test"); res = getSummingItems(arr,tgt); console.timeEnd("test"); console.log("found",res.length,"subsequences summing to",tgt); console.log(JSON.stringify(res)); 
 public class SumOfSubSet { public static void main(String[] args) { // TODO Auto-generated method stub int a[] = {1,2}; int sum=0; if(a.length< =0) { System.out.println(sum); }else { for(int i=0;i 

RUBÍ

Este código rechazará las matrices vacías y devolverá la matriz adecuada con valores.

 def find_sequence(val, num) b = val.length (0..b - 1).map {|n| val.uniq.combination(n).each.find_all {|value| value.reduce(:+) == num}}.reject(&:empty?) end val = [-10, 1, -1, 2, 0] num = 2 

La salida será [[2], [2,0], [- 1,1,2], [- 1,1,2,0]]

Mi solución de retroceso: – Ordene la matriz, luego aplique la vuelta atrás.

 void _find(int arr[],int end,vector &v,int start,int target){ if(target==0){ for(int i = 0;i= arr[i];i++){ v.push_back(arr[i]); _find(arr,end,v,i+1,target-arr[i]); v.pop_back(); } } } 

Si bien es sencillo determinar si se trata de un subconjunto o no que sum al objective, la implementación se vuelve complicada cuando se necesita realizar un seguimiento de los subconjuntos parciales considerados.

Si utiliza una lista vinculada, un conjunto de hash o cualquier otra colección genérica, estaría tentado de agregar un elemento a esta colección antes de la llamada que incluye el artículo, y luego eliminarlo antes de la llamada que excluye el artículo. Esto no funciona como se esperaba, ya que los marcos de stack en los que se producirá el agregado no son los mismos en los que se producirá la eliminación.

La solución es usar una cadena para hacer un seguimiento de la secuencia. Se agrega a la cadena se puede hacer en línea en la llamada a la función; por lo tanto, manteniendo el mismo marco de stack y su respuesta se conformaría maravillosamente a la estructura recursiva original de hasSubSetSum.

 import java.util.ArrayList; 

Solución de clase pública {

 public static boolean hasSubSet(int [] A, int target) { ArrayList subsets = new ArrayList<>(); helper(A, target, 0, 0, subsets, ""); // Printing the contents of subsets is straightforward return !subsets.isEmpty(); } private static void helper(int[] A, int target, int sumSoFar, int i, ArrayList subsets, String curr) { if(i == A.length) { if(sumSoFar == target) { subsets.add(curr); } return; } helper(A, target, sumSoFar, i+1, subsets, curr); helper(A, target, sumSoFar + A[i], i+1, subsets, curr + A[i]); } public static void main(String [] args) { System.out.println(hasSubSet(new int[] {1,2,4,5,6}, 8)); } 

}