Permutations
最后更新于:2022-04-02 01:12:06
# Permutations
### Source
- leetcode: [Permutations | LeetCode OJ](https://leetcode.com/problems/permutations/)
- lintcode: [(15) Permutations](http://www.lintcode.com/en/problem/permutations/)
### Problem
Given a list of numbers, return all possible permutations.
#### Example
For nums = `[1,2,3]`, the permutations are:
~~~
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
~~~
#### Challenge
Do it without recursion.
### 题解1 - Recursion(using subsets template)
排列常见的有数字全排列,字符串排列等。
使用之前 [Subsets](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/subsets.html) 的模板,但是在取结果时只能取`list.size() == nums.size()`的解,且在添加list元素的时候需要注意除重以满足全排列的要求。此题假设前提为输入数据中无重复元素。
### Python
~~~
class Solution:
"""
@param nums: A list of Integers.
@return: A list of permutations.
"""
def permute(self, nums):
alist = []
result = [];
if not nums:
return result
self.helper(nums, alist, result)
return result
def helper(self, nums, alist, ret):
if len(alist) == len(nums):
# new object
ret.append([] + alist)
return
for i, item in enumerate(nums):
if item not in alist:
alist.append(item)
self.helper(nums, alist, ret)
alist.pop()
~~~
### C++
~~~
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector > permute(vector nums) {
vector > result;
if (nums.empty()) {
return result;
}
vector list;
backTrack(result, list, nums);
return result;
}
private:
void backTrack(vector > &result, vector &list, \
vector &nums) {
if (list.size() == nums.size()) {
result.push_back(list);
return;
}
for (int i = 0; i != nums.size(); ++i) {
// remove the element belongs to list
if (find(list.begin(), list.end(), nums[i]) != list.end()) {
continue;
}
list.push_back(nums[i]);
backTrack(result, list, nums);
list.pop_back();
}
}
};
~~~
### Java
~~~
public class Solution {
public List
';
- > permute(int[] nums) {
List
- > result = new ArrayList
- >();
if (nums == null || nums.length == 0) return result;
List
- > result) {
if (list.size() == nums.length) {
result.add(new ArrayList
- > permute(int[] nums) {
List
- > result = new ArrayList
- >();
List
- > resTemp = permute(numsNew);
for (List
- > permute(int[] nums) {
List
- > result = new ArrayList
- >();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
while (true) {
// step0: add nums into result
List