# 46. Permutations

Given an array `nums` of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

``````Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
``````

Example 2:

``````Input: nums = [0,1]
Output: [[0,1],[1,0]]
``````

Example 3:

``````Input: nums = [1]
Output: [[1]]
``````

Constraints:

• `1 <= nums.length <= 6`
• `-10 <= nums[i] <= 10`
• All the integers of `nums` are unique.

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur, visited(nums.size());
dfs(nums, 0, visited, cur, res);
return res;
}
void dfs(vector<int>& nums, int level, vector<int>& visited, vector<int>& cur, vector<vector<int>>& res) {
if (level == nums.size()) {
res.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 1) continue;
visited[i] = 1;
cur.push_back(nums[i]);
dfs(nums, level + 1, visited, cur, res);
cur.pop_back();
visited[i] = 0;
}
}
};
``````

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
dfs(nums, 0, res);
return res;
}
void dfs(vector<int>& nums, int start, vector<vector<int>>& res) {
if (start >= nums.size()) res.push_back(nums);
for (int i = start; i < nums.size(); ++i) {
swap(nums[start], nums[i]);
dfs(nums, start + 1, res);
swap(nums[start], nums[i]);
}
}
};
``````

_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3

_ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
if (nums.empty()) return vector<vector<int>>(1);
vector<vector<int>> res;
int first = nums[0];
nums.erase(nums.begin());
vector<vector<int>> words = permute(nums);
for (auto &a : words) {
for (int i = 0; i <= a.size(); ++i) {
a.insert(a.begin() + i, first);
res.push_back(a);
a.erase(a.begin() + i);
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res{{}};
for (int a : nums) {
for (int k = res.size(); k > 0; --k) {
vector<int> t = res.front();
res.erase(res.begin());
for (int i = 0; i <= t.size(); ++i) {
vector<int> one = t;
one.insert(one.begin() + i, a);
res.push_back(one);
}
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
res.push_back(nums);
while (next_permutation(nums.begin(), nums.end())) {
res.push_back(nums);
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/46

Next Permutation

Permutations II

Permutation Sequence

Combinations

https://leetcode.com/problems/permutations/

https://leetcode.com/problems/permutations/discuss/18462/Share-my-three-different-solutions

https://leetcode.com/problems/permutations/discuss/18255/Share-my-short-iterative-JAVA-solution

https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation