1#include <stdio.h>
2
3void swap(int* a, int* b) {
4    int temp = *a;
5    *a = *b;
6    *b = temp;
7}
8
9void backtrack(int* nums, int numsSize, int start, int** result, int* returnSize, int* returnColumnSizes) {
10    if (start == numsSize) {
11        result[*returnSize] = (int*)malloc(sizeof(int) * numsSize);
12        for (int i = 0; i < numsSize; i++) {
13            result[*returnSize][i] = nums[i];
14        }
15        returnColumnSizes[*returnSize] = numsSize;
16        (*returnSize)++;
17    } else {
18        for (int i = start; i < numsSize; i++) {
19            swap(&nums[start], &nums[i]);
20            backtrack(nums, numsSize, start + 1, result, returnSize, returnColumnSizes);
21            swap(&nums[start], &nums[i]);
22        }
23    }
24}
25
26int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
27    int factorial = 1;
28    for (int i = 2; i <= numsSize; i++) {
29        factorial *= i;
30    }
31    int** result = (int**)malloc(sizeof(int*) * factorial);
32    *returnColumnSizes = (int*)malloc(sizeof(int) * factorial);
33    *returnSize = 0;
34    backtrack(nums, numsSize, 0, result, returnSize, *returnColumnSizes);
35    return result;
36}
37
38int main() {
39    int nums[] = {1, 2, 3};
40    int returnSize;
41    int* returnColumnSizes;
42    int** result = permute(nums, 3, &returnSize, &returnColumnSizes);
43    for (int i = 0; i < returnSize; i++) {
44        for (int j = 0; j < returnColumnSizes[i]; j++) {
45            printf("%d ", result[i][j]);
46        }
47        printf("\n");
48    }
49    for (int i = 0; i < returnSize; i++) {
50        free(result[i]);
51    }
52    free(result);
53    free(returnColumnSizes);
54    return 0;
55}
56

1using System;
2using System.Collections.Generic;

public class Permutations {
    public IList<IList<int>> Permute(int[] nums) {
        List<IList<int>> result = new List<IList<int>>();
        Array.Sort(nums);
        do {
            result.Add(new List<int>(nums));
        } while (NextPermutation(nums));
        return result;
    }

    private bool NextPermutation(int[] nums) {
        int i = nums.Length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i < 0) return false;
        int j = nums.Length - 1;
        while (nums[j] <= nums[i]) j--;
        Swap(nums, i, j);
        Array.Reverse(nums, i + 1, nums.Length - i - 1);
        return true;
    }

    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void Main(string[] args) {
        var permutations = new Permutations();
        int[] nums = {1, 2, 3};
        var result = permutations.Permute(nums);
        foreach (var perm in result) {
            Console.WriteLine(string.Join(", ", perm));
        }
    }
}