71 lines
1.2 KiB
C
71 lines
1.2 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
int target;
|
|
int length;
|
|
int *set;
|
|
|
|
void populate_array(int ac, char **av)
|
|
{
|
|
int i = 0;
|
|
int j = 2;
|
|
while(j < ac)
|
|
{
|
|
set[i] = atoi(av[j]);
|
|
i++;
|
|
j++;
|
|
}
|
|
}
|
|
|
|
void print_set(int *used)
|
|
{
|
|
int i = 0;
|
|
int is_first = 1;
|
|
while(i < length)
|
|
{
|
|
if (used[i] == 1)
|
|
{
|
|
if (is_first)
|
|
{
|
|
fprintf(stdout, "%i", set[i]);
|
|
is_first = 0;
|
|
}
|
|
else
|
|
fprintf(stdout, " %i", set[i]);
|
|
}
|
|
i++;
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
void powerset(int index, int current_sum, int *used)
|
|
{
|
|
if (index == length)
|
|
{
|
|
if (current_sum == target)
|
|
print_set(used);
|
|
return ;
|
|
}
|
|
|
|
powerset(index + 1, current_sum, used);
|
|
used[index] = 1;
|
|
powerset(index + 1, current_sum + set[index], used);
|
|
used[index] = 0;
|
|
}
|
|
|
|
int main(int ac, char **av)
|
|
{
|
|
if (ac < 2)
|
|
return (1);
|
|
|
|
length = ac -2;
|
|
target = atoi(av[1]);
|
|
set = (int *) malloc (sizeof(int) * length);
|
|
int *used = (int *) calloc (length, sizeof(int));
|
|
populate_array(ac, av);
|
|
powerset(0, 0, used);
|
|
free(set);
|
|
free(used);
|
|
return (0);
|
|
|
|
} |