LeetCode //C - 46. Permutations

46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

From: LeetCode
Link: 46. Permutations

---

Solution:

Ideas：

The basic idea behind this solution is a recursive backtracking approach to generate all possible permutations for the input array nums. At each step of the recursion, we consider each number in the array for the current position and then recursively generate permutations for the remaining numbers.

Key Components:

1. swap function:
This is a simple utility function that swaps two numbers in the array.

2. generatePermutations function:
This function is where the main logic resides. It takes the following parameters:

• nums: The input array.
• numsSize: The size of the input array.
• start: The starting index for generating permutations.
• result: The 2D array where we store all the permutations.
• returnSize: A pointer to an integer that keeps track of the number of permutations generated so far.

The logic works as follows:

• If start is equal to numsSize, it means we have a valid permutation of the array. So, we copy the current permutation into the result array and increment the returnSize.
• Otherwise, for each index i from start to numsSize-1, we swap the numbers at indices start and i, and then recursively call generatePermutations with start + 1. After the recursive call, we swap the numbers back (backtrack) to restore the original array order. This ensures that we explore all possible configurations for the array.

3. permute function:
This is the main function that is called by the user. It sets up the necessary data structures and then calls generatePermutations to generate all permutations. The steps are:

• Calculate the maximum number of permutations possible for an array of size numsSize. This is simply numsSize! (factorial of numsSize).
• Allocate memory for the result 2D array based on the maximum number of permutations.
• Allocate memory for the returnColumnSizes array and set all its values to numsSize since all permutations will have the same size.
• Call generatePermutations to fill the result array with all permutations.
• Return the result array.

Code:

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
void swap(int* nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void generatePermutations(int* nums, int numsSize, int start, int** result, int* returnSize) {
    if (start == numsSize) {
        result[*returnSize] = (int*)malloc(numsSize * sizeof(int));
        for (int i = 0; i < numsSize; i++) {
            result[*returnSize][i] = nums[i];
        }
        (*returnSize)++;
        return;
    }
    for (int i = start; i < numsSize; i++) {
        swap(nums, start, i);
        generatePermutations(nums, numsSize, start + 1, result, returnSize);
        swap(nums, start, i); // backtrack
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int maxPermutations = 1;
    for (int i = 1; i <= numsSize; i++) {
        maxPermutations *= i;
    }

    int** result = (int**)malloc(maxPermutations * sizeof(int*));
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(maxPermutations * sizeof(int));
    for (int i = 0; i < maxPermutations; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }

    generatePermutations(nums, numsSize, 0, result, returnSize);
    
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44