106 lines
2.8 KiB
C
106 lines
2.8 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
// Função auxiliar para imprimir um subconjunto encontrado.
|
|
// A ordem dos elementos é mantida porque os adicionamos na ordem original.
|
|
void print_subset(int *subset, int size)
|
|
{
|
|
int i;
|
|
|
|
i = 0;
|
|
while (i < size)
|
|
{
|
|
printf("%d", subset[i]);
|
|
if (i < size - 1)
|
|
printf(" ");
|
|
i++;
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
/**
|
|
* Função recursiva de backtracking para encontrar os subconjuntos.
|
|
*
|
|
* @param target A soma restante que precisamos alcançar.
|
|
* @param set O conjunto original de números.
|
|
* @param set_size O tamanho do conjunto original.
|
|
* @param index O índice do elemento atual que estamos considerando no conjunto.
|
|
* @param current_path O subconjunto que estamos construindo atualmente.
|
|
* @param path_len O número de elementos no subconjunto atual.
|
|
*/
|
|
void find_subsets(int target, int *set, int set_size, int index, int *current_path, int path_len)
|
|
{
|
|
// Caso base 1: Encontramos um subconjunto cuja soma é igual ao alvo original.
|
|
if (target == 0)
|
|
{
|
|
print_subset(current_path, path_len);
|
|
// Retornamos porque encontramos uma solução válida para este caminho.
|
|
return;
|
|
}
|
|
|
|
// Caso base 2: Se já consideramos todos os números, não há mais nada a fazer.
|
|
if (index >= set_size)
|
|
{
|
|
return;
|
|
}
|
|
|
|
// --- Decisão Recursiva ---
|
|
|
|
// Escolha 1: INCLUIR o elemento atual (set[index]) no subconjunto.
|
|
// Adicionamos o elemento ao nosso caminho.
|
|
current_path[path_len] = set[index];
|
|
// Chamamos a função para o próximo elemento, com o alvo reduzido.
|
|
find_subsets(target - set[index], set, set_size, index + 1, current_path, path_len + 1);
|
|
|
|
// Escolha 2: NÃO INCLUIR o elemento atual (set[index]).
|
|
// Este é o passo de "backtrack". Nós simplesmente ignoramos o elemento atual
|
|
// e passamos para o próximo, sem alterar o caminho ou o alvo.
|
|
find_subsets(target, set, set_size, index + 1, current_path, path_len);
|
|
}
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
int target;
|
|
int *numbers;
|
|
int *path;
|
|
int size;
|
|
int i;
|
|
|
|
// Deve haver pelo menos um alvo (n). O conjunto (s) pode ser vazio.
|
|
if (argc < 2)
|
|
return (0);
|
|
|
|
target = atoi(argv[1]);
|
|
size = argc - 2;
|
|
|
|
// Aloca memória para o conjunto de números de entrada.
|
|
numbers = (int *)malloc(sizeof(int) * size);
|
|
if (!numbers)
|
|
return (1); // Erro de malloc
|
|
|
|
// Aloca memória para o array que armazenará o subconjunto atual.
|
|
// O tamanho máximo de um subconjunto é o tamanho do conjunto original.
|
|
path = (int *)malloc(sizeof(int) * size);
|
|
if (!path)
|
|
{
|
|
free(numbers);
|
|
return (1); // Erro de malloc
|
|
}
|
|
|
|
// Converte os argumentos da linha de comando em um array de inteiros.
|
|
i = 0;
|
|
while (i < size)
|
|
{
|
|
numbers[i] = atoi(argv[i + 2]);
|
|
i++;
|
|
}
|
|
|
|
// Inicia a busca recursiva a partir do primeiro elemento (índice 0).
|
|
find_subsets(target, numbers, size, 0, path, 0);
|
|
|
|
// Libera a memória alocada.
|
|
free(numbers);
|
|
free(path);
|
|
|
|
return (0);
|
|
} |