全排列
题目要求
编写一个算法，输入一个不包含重复数字的数组 nums，输出这个数组的所有可能的全排列。结果可以按照任意顺序返回。
解题思路
全排列问题是一个经典的递归问题，可以通过回溯算法来解决。回溯算法可以看作是通过试错来寻找所有可能解的算法，如果当前选择不满足条件，则回退到上一步进行重新选择，这个过程可以用递归函数来实现。
解决这个问题的步骤如下：
-
初始化路径： 创建一个空列表
path，用于存储单个排列的路径。 -
递归与回溯： 设计一个递归函数，该函数接受当前路径
path和一个待选择的数字列表options作为参数。每次递归调用都会尝试将options列表中的一个数字添加到path中。 -
选择与撤销选择： 在递归函数中，遍历
options列表，对于每个数字，我们做出选择，将其加入到path中，并从options中移除，然后递归调用函数。递归返回后，需要撤销之前的选择，将数字从path中移除，并放回options中，以便进行下一次选择。 -
终止条件： 当
options列表为空时，说明已经完成了一个全排列的构建，此时将path添加到结果列表中。 -
返回结果： 递归完成后，返回存储所有全排列的结果列表。
通过这种方式，我们可以遍历所有可能的排列组合，直到所有数字都被使用过，从而得到所有的全排列。
Golang 版本
package main
import "fmt"
func permute(nums []int) [][]int {
var res [][]int
var path []int
used := make([]bool, len(nums))
var backtrack func()
backtrack = func() {
if len(path) == len(nums) {
// Make a deep copy of the path, as it will be reused
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
for i, num := range nums {
if !used[i] {
// Make a choice
path = append(path, num)
used[i] = true
// Enter the next level of decision tree
backtrack()
// Undo the choice
path = path[:len(path)-1]
used[i] = false
}
}
}
backtrack()
return res
}
func main() {
nums := []int{1, 2, 3}
allPermutations := permute(nums)
fmt.Println(allPermutations)
}
这段代码定义了一个 permute 函数，它接受一个整数数组 nums 并返回该数组的所有全排列。在 main 函数中，我们定义了一个示例数组 nums，调用 permute 函数，并打印出所有的全排列。代码中使用了回溯算法的框架，通过递归函数 backtrack 来生成所有可能的排列。
C++版本
#include <iostream>
#include <vector>
void backtrack(std::vector<int>& nums, std::vector<std::vector<int>>& result, std::vector<int>& permutation, std::vector<bool>& chosen) {
if (permutation.size() == nums.size()) {
result.push_back(permutation);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (chosen[i]) continue;
chosen[i] = true;
permutation.push_back(nums[i]);
backtrack(nums, result, permutation, chosen);
chosen[i] = false;
permutation.pop_back();
}
}
std::vector<std::vector<int>> permute(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::vector<int> permutation;
std::vector<bool> chosen(nums.size(), false);
backtrack(nums, result, permutation, chosen);
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3};
std::vector<std::vector<int>> result = permute(nums);
for (const auto& perm : result) {
for (int num : perm) {
std::cout << num << ' ';
}
std::cout << std::endl;
}
return 0;
}
这段 C++代码实现了一个 permute 函数，它接受一个整数向量 nums 并返回该向量的所有全排列。在 main 函数中，我们定义了一个示例向量 nums，调用 permute 函数，并打印出所有的全排列。代码中使用了回溯算法的框架，通过递归函数 backtrack 来生成所有可能的排列。在 backtrack 函数中，我们通过一个布尔向量 chosen 来记录哪些数字已经被选择过，以避免重复选择。
Python 版本
from typing import List
def permute(nums: List[int]) -> List[List[int]]:
def backtrack(first=0):
# if all integers are used up
if first == n:
output.append(nums[:])
for i in range(first, n):
# place i-th integer first
# in the current permutation
nums[first], nums[i] = nums[i], nums[first]
# use next integers to complete the permutations
backtrack(first + 1)
# backtrack
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
output = []
backtrack()
return output
# Example usage:
if __name__ == '__main__':
nums = [1, 2, 3]
print(permute(nums))
这段 Python 代码定义了一个 permute 函数，它接受一个整数列表 nums 并返回该列表的所有全排列。在 permute 函数中，我们定义了一个嵌套的 backtrack 函数，它使用递归来生成全排列。backtrack 函数通过交换元素的方式，将每个元素都尝试放在当前排列的第一个位置，然后递归地处理剩余的位置。当达到排列的末尾时，将当前排列复制到输出列表中。在 backtrack 函数中，我们通过交换回来的操作来撤销之前的选择，这样就可以进行新的排列组合。在 if __name__ == '__main__': 部分，我们提供了一个示例用法，创建了一个列表 nums，调用 permute 函数，并打印出所有的全排列。
Java 版本
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
backtrack(nums, new boolean[nums.length], new ArrayList<>(), results);
return results;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> results) {
if (current.size() == nums.length) {
results.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
current.add(nums[i]);
backtrack(nums, used, current, results);
current.remove(current.size() - 1);
used[i] = false;
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
List<List<Integer>> permute = solution.permute(nums);
for (List<Integer> perm : permute) {
for (int num : perm) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
这段 Java 代码定义了一个 Solution 类，其中包含了一个 permute 方法，用于计算一个数组的所有排列组合。permute 方法接受一个整数数组 nums 作为输入，并返回一个列表，其中包含所有可能的排列。
在 Solution 类中，还定义了一个私有的辅助方法 backtrack，它使用回溯算法来生成所有的排列。这个方法接受当前的数组 nums，一个布尔数组 used 来跟踪哪些数字已经被使用过，一个当前排列的列表 current，以及一个结果列表 results。
main 方法中创建了 Solution 的一个实例，并调用 permute 方法，然后打印出所有的排列结果。
Rust 版本
use std::collections::HashSet; fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> { let mut results = Vec::new(); let mut current = Vec::new(); let mut used = HashSet::new(); backtrack(&nums, &mut used, &mut current, &mut results); results } fn backtrack(nums: &Vec<i32>, used: &mut HashSet<i32>, current: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) { if current.len() == nums.len() { results.push(current.clone()); return; } for &num in nums { if !used.contains(&num) { used.insert(num); current.push(num); backtrack(nums, used, current, results); current.pop(); used.remove(&num); } } } fn main() { let nums = vec![1, 2, 3]; let permutations = permute(nums); for p in permutations { println!("{:?}", p); } }
这段 Rust 代码实现了一个 permute 函数，它接受一个整数向量 nums 并返回该向量的所有全排列。在 permute 函数中，我们定义了一个嵌套的 backtrack 函数，它使用递归来生成全排列。backtrack 函数通过使用一个 HashSet 来跟踪哪些数字已经被使用过，从而避免重复。
在 main 函数中，我们创建了一个向量 nums，调用 permute 函数，并打印出所有的全排列。
总结
上述解法采用了回溯算法来求解不含重复数字的数组的所有可能全排列问题。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会丢弃该解，即回溯并且尝试另一种可能的解。
在这个问题中，算法的核心思想是：
- 从数组的第一个位置开始，递归地将每个数字放到当前位置，并对剩余的数字进行全排列。
- 通过递归调用自身，继续这个过程，直到当前排列中包含所有的数字。
- 每次递归调用都会尝试数组中的每个尚未使用的数字，以确保生成所有可能的排列。
- 当达到递归的底部，即当前排列包含所有数字时，将其添加到结果集中。
- 在每次递归返回之前，需要撤销上一步的操作，以便回溯到上一步的状态，这通常通过移除当前排列的最后一个数字和更新使用状态来实现。
在不同的编程语言实现中，可能会使用不同的数据结构来跟踪哪些数字已经被使用过。例如，在 C++和 Java 实现中，通常使用一个布尔数组来标记哪些数字已经被放入当前排列中。而在 Rust 实现中，则使用了HashSet来存储已经被使用的数字。
无论使用哪种编程语言，算法的基本框架和逻辑是相同的，都是通过递归和回溯来实现的。