encontrar todos os subconjuntos que summ um determinado valor

Dado um conjunto de números: {1, 3, 2, 5, 4, 9}, encontre o número de subconjuntos que summ um valor específico (digamos, 9 para este exemplo).

Isso é semelhante ao problema da sum do subconjunto com a pequena diferença de que, em vez de verificar se o conjunto tem um subconjunto que sum 9, precisamos encontrar o número desses subconjuntos. Eu estou seguindo a solução para o problema da sum do subconjunto aqui . Mas e eu estou querendo saber como eu posso modificá-lo para retornar a contagem 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) 

    Explicação

    Este é um dos problemas clássicos. A ideia é encontrar o número de sums possíveis com o número atual. E é verdade que, existe exatamente uma maneira de trazer a sum para 0. No começo, temos apenas um número. Começamos a partir do nosso alvo (variável Máximo na solução) e subtraímos esse número. Se for possível obter uma sum desse número (o elemento da matriz correspondente a esse número não é zero), adicione-o ao elemento da matriz correspondente ao número atual. O programa seria mais fácil de entender dessa maneira

     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] 

    Quando o número é 1, existe apenas uma maneira em que você pode chegar à sum de 1 (1-1 se torna 0 e o elemento correspondente a 0 é 1). Então o array seria assim (lembre-se que o elemento zero terá 1)

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

    Agora, o segundo número é 2. Começamos subtraindo 2 de 9 e não é válido (já que o elemento array de 7 é zero, pulamos isso) continuamos fazendo isso até 3. Quando seu 3, 3 – 2 é 1 e o elemento da matriz correspondente a 1 é 1 e nós o adicionamos ao elemento array de 3. e quando seu 2, 2 – 2 se torna 0 e nós o valor corresponde a 0 ao elemento array de 2. Após esta iteração o array se parece com isto

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

    Continuamos fazendo isso até processarmos todos os números e o array depois que cada iteração se parecer com isso

     [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] 

    Após a última iteração, consideraríamos todos os números e o número de maneiras de obter o destino seria o elemento da matriz correspondente ao valor de destino. No nosso caso, Array [9] após a última iteração é 8.

    Você pode usar a Programação Dinâmica. A complexidade do algoritmo é O (Sum * N) e usa a memory O (Sum) .

    Aqui está minha implementação em 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 o número de subconjuntos pode ter valor 2 ^ N, isso pode sobrecarregar o tipo int.

    Algo funciona apenas para números positivos.

    Aqui está uma Java Solution :

    Este é um problema clássico de rastreamento de retorno para encontrar todos os subconjuntos possíveis da matriz inteira ou conjunto que é a input e, em seguida, filtering aqueles que summ a target

     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++; } } } 

    Ele fornece valores separados por espaço dos subconjuntos que summ um destino.

    Imprimiria valores separados por comutação para os subconjuntos que summ 25 em {24, 1, 15, 3, 4, 15, 3}

    1) 24 1

    2) 3 4 15 3

    3) 15 3 4 3

    O mesmo site geeksforgeeks também discute a solução para produzir todos os subconjuntos que summ um valor em particular: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/

    No seu caso, em vez dos conjuntos de saída, você só precisa contá-los. Certifique-se de verificar a versão otimizada na mesma página, pois é um problema NP-completo .

    Essa questão também foi perguntada e respondida antes em stackoverflow sem mencionar que é um problema de sum de subconjunto: Localizando todas as combinações possíveis de números para atingir uma determinada sum

    Este meu programa em ruby. Ele retornará matrizes, cada uma contendo as subseqüências que summ o valor alvo fornecido.

     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 

    Eu resolvi isso por java. Essa solução é bem simples.

     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 

    A solução usual de DP é verdadeira para o problema.

    Uma otimização que você pode fazer é manter uma contagem de quantas soluções existem para a sum específica, em vez dos conjuntos reais que compõem essa sum …

    Esta minha implementação de programação dinâmica no JS. Ele retornará uma matriz de matrizes, cada uma contendo as subseqüências que summ o valor alvo fornecido.

     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 

    RUBI

    Esse código rejeitará as matrizes vazias e retornará a matriz adequada com 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 

    A saída será [[2], [2,0], [- 1,1,2], [- 1,1,2,0]]

    Minha solução de backtracking: – Ordene o array e aplique o backtracking.

     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(); } } } 

    Embora seja fácil descobrir se o subconjunto deles é ou não equivalente ao destino, a implementação fica complicada quando você precisa acompanhar os subconjuntos parciais em consideração.

    Se você usar uma linked list, um conjunto de hash ou qualquer outra coleção genérica, você será tentado a adicionar um item a essa coleção antes da chamada que inclui o item e, em seguida, removê-lo antes da chamada que exclui o item. Isso não funciona como esperado, como os frameworks de pilha em que o adicionar ocorrerá não é o mesmo que aquele em que a remoção ocorrerá.

    A solução é usar uma string para acompanhar a sequência. Anexa à string pode ser feita inline na chamada de function; mantendo assim o mesmo quadro de pilha e sua resposta, em seguida, iria se ajustar lindamente à estrutura recursiva hasSubSetSum original.

     import java.util.ArrayList; 

    public class Solution {

     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)); } 

    }