【每日一题】46. Permutations
题目描述
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]给定一个 没有重复 数字的序列，返回其所有可能的全排列。
题解
典型的递归问题。1、2、 3的全排列，可以分为以1开头，2、 3的全排列；2开头，1，3的全排列；3开头，1,2的全排列。缩小的问题，和原问题相比，只是规模缩小了，问题的求解方式没有发生变化。
对于以1开头的子问题，可以不断缩小，直到剩下一个元素，它的排列时唯一的，然后向上“归”。
自己大脑模拟操作：首先固定1，找到以1开头的所有排列；对于2,3，类似，依次固定2,3，这样我们就找到了一个排列；之后，调换2、3顺序，就找到了另一个排列；然后找以2开头的所有排列，依次类推。
这里，我们定义dfs递归函数，通过参数i表示，当前的排列的下标；当下标超过数组范围时，说明已经找到了一个排列，将这个排列添加到结果数组中；通过不断递归调用，即可得到最终的答案。
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
dfs(nums, result, 0);
return result;
}
void dfs(vector<int>& nums, vector<vector<int>>& res, int i){
if (i >= nums.size()){//终止条件
res.push_back(nums);
return;
}
for(int j=i; j< nums.size(); j++){
swap(nums[i], nums[j]);
dfs(nums, res, i+1);
swap(nums[i], nums[j]);
}
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录