给定一个不包含重复的数组，返回所有可能的排列

这是一个经典的排列问题，可以通过回溯算法来解决。下面是 Python 代码实现：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first):
            if first == n:
                res.append(nums[:])
            for i in range(first, n):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]
                
        n = len(nums)
        res = []
        backtrack(0)
        return res

算法的时间复杂度为 $O(n \times n!)$，其中 $n$ 是数组的长度。因为共有 $n!$ 种不同的排列，每种排列需要 $O(n)$ 的时间来生成。空间复杂度为 $O(n)$，因为我们需要一个列表来存储每个排列。

相关问题

给定一个不包含重复的数组，返回所有可能的排列。

这道题可以使用回溯法来解决。

具体思路是，从第一个位置开始，依次将每个元素放在第一个位置，然后递归地求解剩下元素的排列，直到最后一个位置。在递归过程中，需要记录已经放置的元素，以及还未放置的元素，用于回溯时恢复状态。

下面是 Python 代码实现：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []

        def backtrack(start):
            if start == n:
                res.append(nums[:])
                return
            for i in range(start, n):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]

        backtrack(0)
        return res

其中，backtrack 函数表示从第 start 个位置开始求解排列。在 for 循环中，依次将第 i 个元素放在第 start 个位置，然后递归地求解剩下元素的排列。在递归结束后，需要将元素交换回来，进行回溯。最后返回所有可能的排列。

时间复杂度为 O(n!)，因为一共有 n! 种排列；空间复杂度为 O(n)，因为需要记录未放置的元素。

给定一个不包含重复的数组，返回所有可能的排列。C语言

以下是使用递归实现的C语言代码：

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

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void permute(int *nums, int start, int end) {
    if (start == end) {
        for (int i = 0; i <= end; i++) {
            printf("%d ", nums[i]);
        }
        printf("\n");
    } else {
        for (int i = start; i <= end; i++) {
            swap(&nums[start], &nums[i]);
            permute(nums, start + 1, end);
            swap(&nums[start], &nums[i]);
        }
    }
}

int main() {
    int nums[] = {1, 2, 3};
    int n = sizeof(nums) / sizeof(nums[0]);

    permute(nums, 0, n - 1);

    return 0;
}

输出：

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 

该算法的时间复杂度为O(n!)，因为有n!种可能的排列。