https://leetcode.com/problems/permutations/
Permutations
Total Accepted: 70053 Total Submissions: 214523 Difficulty: Medium
Given a collection of numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Code
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return []
res = []
self.recur(nums, 0, res)
return res
def recur(self, nums, pos, res):
if pos == len(nums):
res.append(nums[:])
for i in xrange(pos, len(nums)):
nums[i], nums[pos] = nums[pos], nums[i]
self.recur(nums, pos+1, res)
nums[i], nums[pos] = nums[pos], nums[i]
Idea
We can observe the following process to obtain permutations:
1’s permutation = 1
{1,2}’s permutation = {1,2} and {2,1}. Essentially, it is 1+{2}’s permutation and 2+{1}’s permutation
{1,2,3}’s permutation = 1+{2,3}’s permutation, 2+{1,3}’s permutation, 3+{2,1}’s permutation.
Therefore we can obtain all the permutations by:
- swap the first element with any element after it.
- get the permutation of nums[1:]
We can recursively do this to get the result.