C Language Algorithm – Permutation Problem

Today's algorithm problem is to solve the "permutation" algorithm using C language. Here are my algorithm ideas and implementation. Let's take a look.
Algorithm Problem
Given an array of integers nums without duplicate numbers, return all possible permutations. A permutation is a unique reordering of the elements in an array.
Algorithm Idea
To solve the permutation problem, we can use a recursive algorithm to generate all possible permutations.
The specific steps of the algorithm are as follows:
1. Create a helper function permuteHelper to recursively generate permutations.
2. In the permuteHelper function, first check if a permutation has been generated; if so, store the current permutation in the result array.
3. Otherwise, starting from the beginning of the array, swap the current position with each of the following elements to generate all possible permutations.
4. After each swap, continue to recursively call the permuteHelper function to generate the permutations of the remaining positions.
5. After the recursive call ends, restore the state of the array to allow for the next swap to generate other permutations.

👇 Click to receive 👇
👉 C Language Knowledge Resource Collection

Code Implementation

Here is an example code that implements the "permutation" algorithm in C:
#include <stdio.h>#include <stdbool.h>
// Swap two elements in the array
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// Recursive function to generate all possible permutations
void permuteHelper(int* nums, int start, int end, int** result, int* resultSize) {
    if (start == end) {
        // The current permutation has been generated, store it in the result array
        result[*resultSize] = (int*)malloc(end * sizeof(int));
        memcpy(result[*resultSize], nums, end * sizeof(int));
        (*resultSize)++;
        return;
    }
    for (int i = start; i < end; i++) {
        // Swap the i-th element with the start element
        swap(&nums[i], &nums[start]);
        // Recursively generate permutations
        permuteHelper(nums, start + 1, end, result, resultSize);
        // Restore the array for the next permutation
        swap(&nums[i], &nums[start]);
    }
}
// Entry function for permutations
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // Calculate the number of possible permutations
    int totalPermutations = 1;
    for (int i = 1; i <= numsSize; i++) {
        totalPermutations *= i;
    }
    // Allocate memory for result array and column sizes array
    int** result = (int**)malloc(totalPermutations * sizeof(int*));
    *returnColumnSizes = (int*)malloc(totalPermutations * sizeof(int));
    *returnSize = 0;
    // Generate permutations
    permuteHelper(nums, 0, numsSize, result, returnSize);
    // Set the column size for each permutation to numsSize
    for (int i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }
    return result;
}
Algorithm Analysis
Time Complexity: The time complexity of the algorithm depends on the number of permutations generated, which is O(n!), where n is the size of the array.
Space Complexity: The space complexity of the algorithm is O(n!), as we need to store all possible permutations.
Example and Testing

Example Input:
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 Output:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Conclusion
Through the recursive algorithm, we implemented the code to solve the permutation algorithm problem in C language. The permutation problem is a classic algorithm problem, and through this article, I hope to help you understand the application of recursive algorithms.

• C Language Tutorial – Detailed Explanation of Prime Number Program in C Language

• C Language Algorithm – Combination Sum II Algorithm Problem

• C++ Tutorial – First C++ Program