视频字幕
全排列是组合数学中的重要概念。对于包含n个不同元素的集合，全排列的总数为n的阶乘。例如，对于数组[1,2,3]，共有3!=6种不同的排列方式。在Java编程中，我们通常使用回溯算法来生成所有可能的排列。
回溯算法是解决全排列问题的经典方法。它的核心思想是构建一个决策树：从根节点开始，每一层代表选择一个元素的位置。当我们选择了一个元素后，就递归地处理剩余元素。如果当前路径无法得到有效解，就回退到上一步，尝试其他选择。这种"试探-回退"的过程确保我们能遍历所有可能的排列组合。
这是Java实现全排列的核心代码。backtrack方法是递归函数的核心。首先检查当前排列是否达到目标长度，如果是则保存结果。然后遍历所有元素，跳过已使用的元素。对于未使用的元素，将其添加到当前排列中，标记为已使用，然后递归调用。递归返回后，需要撤销选择：移除刚添加的元素，并将其标记为未使用，这样就能探索其他可能的排列。
让我们通过一个具体例子来看执行过程。对于数组[1,2,3]，算法首先选择元素1，然后在剩余元素[2,3]中选择2，最后选择3，得到第一个排列[1,2,3]。接着回溯，撤销对3的选择，选择2，得到[1,3,2]。继续回溯到根节点，选择元素2开始新的分支。这个过程中，used数组动态标记哪些元素已被使用，确保不会重复选择同一个元素。
最后我们来分析全排列算法的复杂度。时间复杂度方面，n个元素的全排列总数为n的阶乘，每生成一个排列需要O(n)的时间来复制数组，所以总时间复杂度是O(n!×n)。空间复杂度主要包括递归栈的O(n)和存储所有结果的O(n!×n)。由于阶乘函数增长极快，这个算法只适用于元素数量较小的情况。掌握回溯算法的思想对解决其他组合优化问题也很有帮助。