46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路

回溯算法

python3解法

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def backtrack(nums, combination):
            if not nums:
                ans.append(combination)
            else:
                for i in range(len(nums)):
                    backtrack(nums[:i]+nums[i+1:], combination+[nums[i]])
        if nums:
            backtrack(nums, [])
        return ans

相似问题：给定一个不包含重复数字的长度为4的序列，能组成多少个互不相同且无重复数字的三位数？
思路

同上，同样是使用回溯算法，与上面不同的是，不是所有数字的全排列，而是三位数的全排列
只需判断组合combination的长度是否等于3，等于3的时候就不再回溯，添加到结果集中

python3解法

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def backtrack(nums, combination):
            if len(combination) == 3:
                ans.append(combination)
            else:
                for i in range(len(nums)):
                    backtrack(nums[:i]+nums[i+1:], combination+[nums[i]])
        if nums:
            backtrack(nums, [])
        return ans

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。