Sponsored
Sponsored
This approach uses recursion combined with backtracking to generate all possible permutations of the input array. The algorithm works by swapping elements of the array and recursively building permutations by fixing one element at a time until the entire array is permutated.
Time Complexity: O(n * n!) as there are n! permutations and we copy each permutation.
Space Complexity: O(n!) for storing the permutations, plus additional space used by the recursive stack.
1
This solution provides a C implementation using the backtracking approach. The backtrack function swaps elements to fix positions and calls itself recursively to generate permutations. Whenever a complete permutation is reached (start == numsSize), it is added to the result list. Swapping is undone as part of backtracking when going back up the call stack.
An alternative iterative approach utilizes a queue to generate permutations level by level by inserting each number at every possible position within every possible permutation.
Time Complexity: O(n * n!), iterating through permutations.
Space Complexity: O(n!) for storing permutations, constant space for current permutation array.
1#include <stdio.h>
2#include <stdlib.h>
3
4void swap(int* a, int* b) {
5 int temp = *a;
6 *a = *b;
7 *b = temp;
8}
9
10int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
11 int factorial = 1;
12 for (int i = 2; i <= numsSize; i++) {
13 factorial *= i;
14 }
15 int** result = (int**)malloc(sizeof(int*) * factorial);
16 *returnColumnSizes = (int*)malloc(sizeof(int) * factorial);
17 *returnSize = 0;
18 int* current = (int*)malloc(sizeof(int) * numsSize);
19
20 for (int i = 0; i < numsSize; i++) {
21 current[i] = nums[i];
22 }
23
24 for (int i = 0; i < factorial; i++) {
25 result[i] = (int*)malloc(sizeof(int) * numsSize);
26 for (int j = 0; j < numsSize; j++) {
27 result[i][j] = current[j];
28 }
29 (*returnColumnSizes)[i] = numsSize;
30
31 int j = numsSize - 1;
32 while (j > 0 && current[j - 1] >= current[j]) {
33 j--;
34 }
35 if (j > 0) {
36 int swapIndex = numsSize - 1;
37 while (current[swapIndex] <= current[j - 1]) {
38 swapIndex--;
39 }
40 swap(¤t[j - 1], ¤t[swapIndex]);
41 }
42 for (int k = j, l = numsSize - 1; k < l; k++, l--) {
43 swap(¤t[k], ¤t[l]);
44 }
45 }
46 free(current);
47 return result;
48}
49
50int main() {
51 int nums[] = {1, 2, 3};
52 int returnSize;
53 int* returnColumnSizes;
54 int** result = permute(nums, 3, &returnSize, &returnColumnSizes);
55 for (int i = 0; i < returnSize; i++) {
56 for (int j = 0; j < returnColumnSizes[i]; j++) {
57 printf("%d ", result[i][j]);
58 }
59 printf("\n");
60 }
61 for (int i = 0; i < returnSize; i++) {
62 free(result[i]);
63 }
64 free(result);
65 free(returnColumnSizes);
66 return 0;
67}
68This C implementation illustrates an iterative method for generating permutations using a next permutation generator. Each permutation is based on modifying and reversing array segments to derive the next permutation sequence, iteratively processed.
Solve with full IDE support and test cases