Equipe Rust Brasil 10 min de leitura

Problema da Soma de Subconjuntos em Rust

Resolva o problema da soma de subconjuntos em Rust com DP: tabela booleana visual, reconstrução de elementos e variantes de partição e contagem.

programação dinâmica subconjuntos soma combinatória rust

O problema da soma de subconjuntos (Subset Sum) é um clássico de programação dinâmica e teoria da complexidade: dado um conjunto de inteiros positivos e um valor alvo, existe algum subconjunto cuja soma é exatamente igual ao alvo? Este é um dos 21 problemas NP-completos originais de Karp e aparece em criptografia, alocação de recursos, balanceamento de carga, planejamento financeiro e como base para problemas de partição.

Nesta página, implementamos a solução completa em Rust com tabela DP booleana, reconstrução dos elementos selecionados e três variantes importantes: partição em dois subconjuntos iguais, contagem de subconjuntos com soma dada e versão com números negativos.

O Problema

Entrada: Um array de inteiros positivos nums[] e um valor alvo.

Objetivo: Determinar se existe um subconjunto de nums cuja soma é exatamente alvo.

Exemplo:

nums = [3, 34, 4, 12, 5, 2]
alvo = 9

Resposta: Sim (subconjunto {4, 5} soma 9)

nums = [3, 34, 4, 12, 5, 2]
alvo = 30

Resposta: Não (nenhum subconjunto soma 30)

Abordagem Ingênua (Força Bruta)

Testamos todos os 2^n subconjuntos:

/// Força bruta: testa todos os subconjuntos.
/// Complexidade: O(2^n) — impraticável para n > ~25.
fn subset_sum_bruta(nums: &[u32], alvo: u32) -> bool {
    fn resolver(nums: &[u32], alvo: u32, i: usize) -> bool {
        // Encontramos a soma alvo!
        if alvo == 0 {
            return true;
        }
        // Sem mais elementos para testar
        if i == 0 {
            return false;
        }

        // Se o elemento atual é maior que o alvo, pule
        if nums[i - 1] > alvo {
            return resolver(nums, alvo, i - 1);
        }

        // Incluir ou não incluir o elemento atual
        resolver(nums, alvo - nums[i - 1], i - 1) || resolver(nums, alvo, i - 1)
    }

    resolver(nums, alvo, nums.len())
}

fn main() {
    let nums = vec![3, 34, 4, 12, 5, 2];
    println!("Soma 9: {}", subset_sum_bruta(&nums, 9));   // true
    println!("Soma 30: {}", subset_sum_bruta(&nums, 30)); // false
}

Identificando Subestrutura Ótima

A recorrência para o subset sum:

dp[i][s] = true se é possível obter soma s usando os primeiros i elementos

dp[i][s] = dp[i-1][s]                           (não incluir nums[i])
         OU dp[i-1][s - nums[i]]                 (incluir nums[i], se nums[i] <= s)

Casos base:
  dp[i][0] = true para todo i  (soma 0: subconjunto vazio)
  dp[0][s] = false para s > 0  (nenhum elemento, soma positiva impossível)
  • Subestrutura ótima: a possibilidade de atingir soma s com i elementos depende de poder atingir s ou s - nums[i] com i-1 elementos.
  • Subproblemas sobrepostos: os mesmos pares (i, s) são verificados múltiplas vezes na recursão.

Visualização da Tabela DP

Para nums = [3, 4, 5, 2] e alvo = 9:

             Soma s -->
             0    1    2    3    4    5    6    7    8    9
           +----+----+----+----+----+----+----+----+----+----+
  {} (0)   |  T |  F |  F |  F |  F |  F |  F |  F |  F |  F |
           +----+----+----+----+----+----+----+----+----+----+
  {3}      |  T |  F |  F |  T |  F |  F |  F |  F |  F |  F |
           +----+----+----+----+----+----+----+----+----+----+
  {3,4}    |  T |  F |  F |  T |  T |  F |  F |  T |  F |  F |
           +----+----+----+----+----+----+----+----+----+----+
  {3,4,5}  |  T |  F |  F |  T |  T |  T |  F |  T |  T |  T |
           +----+----+----+----+----+----+----+----+----+----+
  {3,4,5,2}|  T |  F |  T |  T |  T |  T |  T |  T |  T |  T |
           +----+----+----+----+----+----+----+----+----+----+

T = True (possível), F = False (impossível)

Preenchimento da linha {3,4,5}, s=9:
  Sem 5: dp[{3,4}][9] = F
  Com 5: dp[{3,4}][9-5] = dp[{3,4}][4] = T   <-- {4} soma 4, +5 = 9
  dp[{3,4,5}][9] = F OR T = T

Resultado: dp[4][9] = True (subconjuntos: {4,5} ou {3,4,2})

Complexidade

AbordagemTempoEspaçoObservação
Força BrutaO(2^n)O(n) pilhaNP-completo em geral
Top-Down (Memoização)O(n * S)O(n * S)S = valor alvo
Bottom-Up (Tabulação)O(n * S)O(n * S)Pseudo-polinomial
Otimizado (1 linha)O(n * S)O(S)Percorre de trás para frente

Nota: assim como a mochila, a complexidade é pseudo-polinomial — polinomial em S (valor numérico), não no número de bits para representar S.

Implementação: Top-Down (Memoização)

use std::collections::HashMap;

/// Subset sum com memoização.
fn subset_sum_memo(
    nums: &[u32],
    alvo: u32,
    i: usize,
    cache: &mut HashMap<(usize, u32), bool>,
) -> bool {
    // Soma encontrada!
    if alvo == 0 {
        return true;
    }
    // Sem mais elementos
    if i == 0 {
        return false;
    }

    if let Some(&resultado) = cache.get(&(i, alvo)) {
        return resultado;
    }

    let resultado = if nums[i - 1] > alvo {
        // Elemento não cabe — pula
        subset_sum_memo(nums, alvo, i - 1, cache)
    } else {
        // Inclui ou não inclui
        subset_sum_memo(nums, alvo - nums[i - 1], i - 1, cache)
            || subset_sum_memo(nums, alvo, i - 1, cache)
    };

    cache.insert((i, alvo), resultado);
    resultado
}

fn main() {
    let nums = vec![3, 34, 4, 12, 5, 2];

    let mut cache = HashMap::new();
    println!("Soma 9: {}", subset_sum_memo(&nums, 9, nums.len(), &mut cache));
    // true

    cache.clear();
    println!("Soma 30: {}", subset_sum_memo(&nums, 30, nums.len(), &mut cache));
    // false

    cache.clear();
    println!("Soma 15: {}", subset_sum_memo(&nums, 15, nums.len(), &mut cache));
    // true (3 + 12 ou 4 + 5 + 3 + ... etc.)
}

Implementação: Bottom-Up (Tabulação)

/// Subset sum com tabulação bottom-up.
/// Retorna se é possível e a tabela DP para reconstrução.
fn subset_sum_tabular(nums: &[u32], alvo: usize) -> (bool, Vec<Vec<bool>>) {
    let n = nums.len();

    // dp[i][s] = é possível obter soma s com os primeiros i elementos?
    let mut dp = vec![vec![false; alvo + 1]; n + 1];

    // Caso base: soma 0 é sempre possível (subconjunto vazio)
    for i in 0..=n {
        dp[i][0] = true;
    }

    for i in 1..=n {
        for s in 1..=alvo {
            // Não incluir nums[i-1]
            dp[i][s] = dp[i - 1][s];

            // Incluir nums[i-1] (se couber)
            let valor = nums[i - 1] as usize;
            if valor <= s {
                dp[i][s] = dp[i][s] || dp[i - 1][s - valor];
            }
        }
    }

    (dp[n][alvo], dp)
}

fn main() {
    let nums = vec![3, 34, 4, 12, 5, 2];

    let (possivel, _dp) = subset_sum_tabular(&nums, 9);
    println!("Soma 9: {}", possivel); // true

    let (possivel2, _dp2) = subset_sum_tabular(&nums, 30);
    println!("Soma 30: {}", possivel2); // false

    let (possivel3, _dp3) = subset_sum_tabular(&nums, 15);
    println!("Soma 15: {}", possivel3); // true
}

Otimização de Espaço

Como cada linha depende apenas da anterior, usamos um vetor unidimensional percorrido de trás para frente:

/// Subset sum otimizado: O(n*S) tempo, O(S) espaço.
fn subset_sum_otimizado(nums: &[u32], alvo: usize) -> bool {
    let mut dp = vec![false; alvo + 1];
    dp[0] = true; // Soma 0 é sempre possível

    for &num in nums {
        let valor = num as usize;
        // IMPORTANTE: percorrer de trás para frente!
        // Evita usar o mesmo elemento mais de uma vez.
        for s in (valor..=alvo).rev() {
            if dp[s - valor] {
                dp[s] = true;
            }
        }
    }

    dp[alvo]
}

fn main() {
    let nums = vec![3, 34, 4, 12, 5, 2];
    println!("Soma 9 (otimizado): {}", subset_sum_otimizado(&nums, 9));   // true
    println!("Soma 30 (otimizado): {}", subset_sum_otimizado(&nums, 30)); // false

    // Teste com valores maiores
    let grandes = vec![1, 5, 11, 5];
    println!("Soma 11: {}", subset_sum_otimizado(&grandes, 11)); // true (11 ou 1+5+5)
}

Reconstruindo a Solução

Para identificar quais elementos formam o subconjunto:

/// Reconstrói quais elementos formam o subconjunto com a soma desejada.
fn reconstruir_subconjunto(dp: &[Vec<bool>], nums: &[u32], alvo: usize) -> Option<Vec<u32>> {
    if !dp[nums.len()][alvo] {
        return None;
    }

    let mut resultado = Vec::new();
    let mut s = alvo;
    let n = nums.len();

    for i in (1..=n).rev() {
        // Se dp[i-1][s] é true, não precisamos do item i
        // Se dp[i-1][s] é false, precisamos do item i
        if !dp[i - 1][s] {
            resultado.push(nums[i - 1]);
            s -= nums[i - 1] as usize;
        }
    }

    resultado.reverse();
    Some(resultado)
}

fn main() {
    let nums = vec![3, 34, 4, 12, 5, 2];
    let alvo = 9;

    let (possivel, dp) = subset_sum_tabular(&nums, alvo);
    if possivel {
        if let Some(subconjunto) = reconstruir_subconjunto(&dp, &nums, alvo) {
            let soma: u32 = subconjunto.iter().sum();
            println!("Subconjunto com soma {}: {:?} (verificação: {})", alvo, subconjunto, soma);
        }
    }
    // Subconjunto com soma 9: [4, 5] (verificação: 9)
}

fn subset_sum_tabular(nums: &[u32], alvo: usize) -> (bool, Vec<Vec<bool>>) {
    let n = nums.len();
    let mut dp = vec![vec![false; alvo + 1]; n + 1];
    for i in 0..=n { dp[i][0] = true; }
    for i in 1..=n {
        for s in 1..=alvo {
            dp[i][s] = dp[i - 1][s];
            let v = nums[i - 1] as usize;
            if v <= s { dp[i][s] = dp[i][s] || dp[i - 1][s - v]; }
        }
    }
    (dp[n][alvo], dp)
}

Variante 1: Partição em Dois Subconjuntos Iguais

Um dos problemas mais populares em entrevistas: dado um array, é possível dividi-lo em dois subconjuntos com somas iguais?

/// Verifica se o array pode ser dividido em dois subconjuntos com somas iguais.
/// Reduz-se a: existe subconjunto com soma = soma_total / 2?
fn pode_particionar(nums: &[u32]) -> bool {
    let soma_total: u32 = nums.iter().sum();

    // Se a soma total é ímpar, impossível dividir igualmente
    if soma_total % 2 != 0 {
        return false;
    }

    let metade = (soma_total / 2) as usize;

    // Subset sum para metade
    let mut dp = vec![false; metade + 1];
    dp[0] = true;

    for &num in nums {
        let v = num as usize;
        for s in (v..=metade).rev() {
            if dp[s - v] {
                dp[s] = true;
            }
        }
        // Otimização: se já encontrou, pode parar
        if dp[metade] {
            return true;
        }
    }

    dp[metade]
}

fn main() {
    let nums1 = vec![1, 5, 11, 5];
    println!("Pode particionar {:?}: {}", nums1, pode_particionar(&nums1));
    // true: {1, 5, 5} e {11}

    let nums2 = vec![1, 2, 3, 5];
    println!("Pode particionar {:?}: {}", nums2, pode_particionar(&nums2));
    // false: soma = 11 (ímpar)

    let nums3 = vec![3, 3, 3, 4, 5];
    println!("Pode particionar {:?}: {}", nums3, pode_particionar(&nums3));
    // true: {3, 3, 3} e {4, 5}, ambos somam 9
}

Variante 2: Contar Subconjuntos com Soma Dada

/// Conta quantos subconjuntos somam exatamente o valor alvo.
fn contar_subconjuntos(nums: &[u32], alvo: usize) -> u64 {
    let mut dp = vec![0u64; alvo + 1];
    dp[0] = 1; // Um subconjunto (vazio) soma 0

    for &num in nums {
        let v = num as usize;
        // Percorre de trás para frente para garantir 0/1
        for s in (v..=alvo).rev() {
            dp[s] += dp[s - v];
        }
    }

    dp[alvo]
}

fn main() {
    let nums = vec![1, 2, 3, 4, 5];
    let alvo = 5;
    println!(
        "Subconjuntos de {:?} com soma {}: {}",
        nums, alvo, contar_subconjuntos(&nums, alvo)
    );
    // 3 subconjuntos: {5}, {2,3}, {1,4}

    let nums2 = vec![1, 1, 1, 1, 1];
    let alvo2 = 3;
    println!(
        "Subconjuntos de {:?} com soma {}: {}",
        nums2, alvo2, contar_subconjuntos(&nums2, alvo2)
    );
    // 10 subconjuntos (C(5,3) = 10)
}

Variante 3: Encontrar Todos os Subconjuntos com a Soma

/// Encontra TODOS os subconjuntos que somam o valor alvo.
fn encontrar_todos(nums: &[u32], alvo: u32) -> Vec<Vec<u32>> {
    let mut resultados = Vec::new();
    let mut atual = Vec::new();

    fn backtrack(
        nums: &[u32],
        alvo: u32,
        inicio: usize,
        atual: &mut Vec<u32>,
        resultados: &mut Vec<Vec<u32>>,
    ) {
        if alvo == 0 {
            resultados.push(atual.clone());
            return;
        }

        for i in inicio..nums.len() {
            if nums[i] > alvo {
                continue;
            }
            atual.push(nums[i]);
            backtrack(nums, alvo - nums[i], i + 1, atual, resultados);
            atual.pop();
        }
    }

    backtrack(nums, alvo, 0, &mut atual, &mut resultados);
    resultados
}

fn main() {
    let nums = vec![1, 2, 3, 4, 5, 6, 7];
    let alvo = 10;

    let subconjuntos = encontrar_todos(&nums, alvo);
    println!("Subconjuntos com soma {}:", alvo);
    for s in &subconjuntos {
        println!("  {:?} (soma: {})", s, s.iter().sum::<u32>());
    }
    // {1,2,3,4}, {1,2,7}, {1,3,6}, {1,4,5}, {2,3,5}, {3,7}, {4,6}
}

Exercícios Práticos

  1. Diferença mínima de partição: Divida o array em dois subconjuntos minimizando a diferença absoluta entre suas somas. Dica: encontre a maior soma possível <= soma_total/2 usando subset sum.

  2. Subset Sum com repetição: Cada elemento pode ser usado quantas vezes quiser (mochila ilimitada). Modifique a direção do percorrimento no vetor DP.

  3. Target Sum (+ e -): Dado um array e um alvo, atribua sinais + ou - a cada elemento para que a soma total seja igual ao alvo. Quantas atribuições são possíveis? Dica: reduza a subset sum com alvo_novo = (soma_total + alvo) / 2.

  4. K subconjuntos com somas iguais: Generalize a partição para k subconjuntos (em vez de 2). Para k pequeno, use backtracking com poda; para k = 2, use DP.

Veja Também