Power Set с использованием рекурсии

Question

#include <stdio.h>

void powerSet(int* a, int index, int *curr, int N) {
    if (index == N)
        return;

    printf("(");
    for(int i = 0; i <= index; i++)
        printf("%d, ", curr[i]);

    printf(")\n");
    // processing here.


    int x = index + 1;
    for (int i = index + 1; i < N; i++) {

        curr[x]  = a[i];
        // curr += str[i];
        powerSet(a, i, curr, N);
    }
    return;
}

int main(){

    int a[] = {10,12,14,17};
    int *curr = (int*)malloc(sizeof(int) * 50);
    int n = 4;

    powerSet(&(*a),-1,curr,n);
}

Кажется, есть некоторая логическая ошибка с приведенным выше кодом. Кто-нибудь может указать на это, пожалуйста? Вывод, который вы получаете при запуске кода, выглядит примерно так:

() 
(10, )
(10, 12, )
(10, 12, 14, )
(10, 12, 14, 17, )
(10, 12, 17, 17, )
(10, 14, 17, )
(10, 14, 17, 17, )
(10, 17, 17, 17, )
(12, 17, )
(12, 17, 14, )
(12, 17, 14, 17, )
(12, 17, 17, 17, )
(14, 17, 17, )
(14, 17, 17, 17, )
(17, 17, 17, 17, )

Answer 1

powerSet(a, i, curr, N); неверно. На этом этапе некоторые элементы a были добавлены к curr или использованы ранее и, так или иначе, больше не имеют права на включение. Вызов может быть изменен на powerSet(a+i+1, x, curr, N-i-1);, поэтому первый и четвертый аргументы описывают элементы, оставшиеся для рассмотрения (первый - указатель на то, с чего они начинаются, четвертый - их число), а второй и третий аргументы описывают элементы, находящиеся в настоящее время в рабочем наборе (третий - указатель на то, с чего они начинаются, а второй - на индекс последнего из них, или -1, если их еще нет).

Для адаптации остальных кода для этого изменения, удалите if (index == N) и return; (потому что мы будем знать, что мы закончили, когда N равен нулю, указывая на то, что не осталось элементов для рассмотрения, и финальный l oop будет обрабатывать это естественным образом ) и измените for (int i = index + 1; i < N; i++) на for (int i = 0; i < N; i++) (таким образом, мы l oop по элементам, остающимся подлежащим рассмотрению, который не включает index).