全排列算法详解：递归法和字典序法

全排列是指给定一组数，求出所有可能的排列方式。求全排列有多种方法，以下介绍两种常用的方法：

1. 递归法

递归法可以通过不断交换数组中的元素，得到所有可能的排列方式。具体步骤如下：

• 将数组中的第一个元素依次与后面的元素进行交换，得到所有以第一个元素开头的排列方式。
• 对于每种以第一个元素开头的排列方式，将剩余的元素再次进行交换，得到所有可能的排列方式。

以下是Python代码实现：

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

2. 字典序法

字典序法是通过找到当前排列的下一个排列，不断迭代得到所有排列方式。具体步骤如下：

• 从右往左找到第一个相邻的升序元素对（即nums[i] < nums[i+1]）。
• 在nums[i+1:]中找到大于nums[i]的最小元素nums[j]。
• 交换nums[i]和nums[j]。
• 反转nums[i+1:]。

以下是Python代码实现：

def permute(nums):
    res = []
    nums.sort()
    while True:
        res.append(nums[:])
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1
        if i == -1:
            break
        j = len(nums) - 1
        while j > i and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i+1:] = reversed(nums[i+1:])
    return res

以上两种方法都可以得到所有可能的排列方式，但递归法的时间复杂度更低，因为字典序法需要进行不断的比较和交换操作。