Este artigo demosntra duas técnicas para encontrar combinações em coleeções Java: uma abordagem baseada em bits e uma solução recursiva.

Abordagem Baseada em Bits

A primeira implementação utiliza um padrão de bits para representar combinações. Cada elemento na coleção corresponde a um bit em um array. Quando o bit está ativo (1), o elemento é incluído na combinação atual.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class GeradorCombinacoes {

    public static void main(String[] args) {
        // Exemplo com inteiros
        int[] valores = {1, 2, 3, 4};
        List<Integer> colecaoInteiros = new ArrayList<>();
        for (Integer valor : valores) {
            colecaoInteiros.add(valor);
        }
        
        IteradorCombinacoes<Integer> iteradorInteiros = new IteradorCombinacoes<>(colecaoInteiros);
        while (iteradorInteiros.hasNext()) {
            Object combinacao = iteradorInteiros.next();
            System.out.println(combinacao.toString());
        }
        
        // Exemplo com strings
        String[] frutas = {"maçã", "laranja", "tomate", "batata"};
        List<String> colecaoFrutas = new ArrayList<>();
        for (String fruta : frutas) {
            colecaoFrutas.add(fruta);
        }
        
        IteradorCombinacoes<String> iteradorFrutas = new IteradorCombinacoes<>(colecaoFrutas);
        while (iteradorFrutas.hasNext()) {
            Object combinacao = iteradorFrutas.next();
            System.out.println(combinacao.toString());
        }
    }
}

class IteradorCombinacoes<T> implements Iterator<T> {
    private int[] vetorBits;
    protected final int tamanho;
    protected final List<T> elementosOriginais;
    protected List<T> combinacaoAtual;

    public IteradorCombinacoes(List<T> elementos) {
        this.combinacaoAtual = new ArrayList<>();
        this.tamanho = elementos.size();
        this.vetorBits = new int[tamanho + 2];
        this.elementosOriginais = elementos;
    }

    @Override
    public boolean hasNext() {
        return vetorBits[tamanho + 1] != 1;
    }

    @SuppressWarnings("unchecked")
    @Override
    public T next() {
        combinacaoAtual.clear();
        for (int indice = 1; indice <= tamanho; indice++) {
            if (vetorBits[indice] == 1) {
                T elemento = elementosOriginais.get(indice - 1);
                combinacaoAtual.add(elemento);
            }
        }
        
        int posicao = 1;
        while (vetorBits[posicao] == 1) {
            vetorBits[posicao] = 0;
            posicao++;
        }
        vetorBits[posicao] = 1;
        
        return (T) combinacaoAtual;
    }
}

Abordagem Recursiva

A segunda solução utiliza recursão para encontrar combinações de números em um intervalo específico que somam a um valer alvo.

public static void main(String[] args) {
    encontrarCombinacoes(1, 20, 36);
}

public static void encontrarCombinacoes(int minimo, int maximo, int alvo) {
    gerarCombinacoes(0, minimo, maximo, alvo, new Stack<Integer>());
}

public static void gerarCombinacoes(int somaAtual, int minimo, int maximo, int alvo,
        Stack<Integer> pilha) {
    for (int i = pilha.isEmpty() ? minimo : (Integer) pilha.lastElement() + 1; i < maximo; ++i) {
        int somaTemporaria = somaAtual + i;
        pilha.push(i);
        
        if (somaTemporaria == alvo) {
            System.out.println(pilha + "=" + alvo);
        } else {
            gerarCombinacoes(somaTemporaria, minimo, maximo, alvo, pilha);
        }
        
        pilha.pop();
    }
}

Ambas as abordagens oferecem soluções eficazes para o problema de encontrar combinações, com a primeira sendo mais genérica para qualquer tipo de coleção e a segunda otimizada para problemas numéricos com soma específica.