recursion - 递归 - 打印 uniq 子组

Question

我的代码：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>


void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {

        printf(" %d ", arr[i]);
    }
    printf("\n");

}

void tr8Helper(int* arr, int n, int index, int b, int* used)
{
    if (index == n )
    {

        printArr(arr, n);

    }
    else {

        for (int i = 0; i < b; i++) {

            arr[index] = i;
            tr8Helper(arr, n, index + 1, b, used);
        }


    }

}


void tr8(int num, int b)
{
    int* myArray = (int*)malloc(num * sizeof(int));
    int* used = (int*)malloc(b * sizeof(int));
    tr8Helper(myArray, num, 0, b, used);
}

int main() {
    tr8(3, 3);
}

到目前为止，这是我的代码，这就是我的递归打印 b = 2，n = 3： 此代码 的输出我遇到的麻烦是如何使用“已使用”数组，因此输出将是例如 b= 3 n = 3 请求的输出 我很难考虑如何考虑这个问题，如何从上面考虑。怎么告诉我的recurrion，我用过这个号码，不要再用了。或者只是在打印发生时跳过这一行。请与我分享您的想法和想法，也许还有一些关于您如何处理此类问题的提示

标签： recursiondata-structures

Answer 1

Judging by your input and expected output, I believe when you say "unique subgroups" you are referring to k-permutations. If that is the case, then you simply need to employ the used array (which in your code is passed around, but not actually employed). I added three new lines in tr8Helper; nothing else needs to be changed.

void tr8Helper(int* arr, int n, int index, int b, int* used) {
  if (index == n) {
    printArr(arr, n);
  } else {
    for (int i = 0; i < b; i++) {
      if (!used[i]) {     // (1) do not use i unless it is available
        used[i] = 1;      // (2) mark i as used so we don't use it twice
        arr[index] = i;
        tr8Helper(arr, n, index + 1, b, used);
        used[i] = 0;      // (3) mark i as available so future k-perms can use it
      }
    }
  }
}