1. 题目
2. 解答
给定一个序列,序列中的任意一个数字都可以作为全排列的最后一位。然后,其余位置元素的确定便是剩余元素的一个全排列,也就是一个子问题。
例子中 [1, 2, 3] 的全排列,最后一位可以是 1 或者 2 或者 3。如果最后一位是 3,前两位便是 [1, 2] 的全排列。
我们用递归来实现,变量 k 一开始为序列的长度,每次求解子问题的时候减一。递归终止条件为 k=1,一个元素的全排列只有它自己。
class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
Generate_Premutations(nums, n, n);
return result;
}
void Generate_Premutations(vector<int>& nums, int n, int k)
{
if (k == 1)
{
result.push_back(nums);
return;
}
// 任何一个数字都可以作为全排列的最后一位
for (int i = 0; i < k; i++)
{
int temp = nums[i];
nums[i] = nums[k-1];
nums[k-1] = temp;
// 最后一位数字确定后,余下的是一个全排列的子问题
Generate_Premutations(nums, n, k-1);
// 恢复原数组
temp = nums[i];
nums[i] = nums[k-1];
nums[k-1] = temp;
}
}
};
获取更多精彩,请关注「seniusen」!