46.permutations.md

46. Permutations

中等

https://leetcode-cn.com/problems/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.

相关企业

• 字节跳动|14
• 亚马逊 Amazon|10
• 微软 Microsoft|8
• Facebook|8
• 领英 LinkedIn|6
• 谷歌 Google|5
• 苹果 Apple|4
• 华为|3
• 彭博 Bloomberg|2
• 高盛集团 Goldman Sachs|2

相关标签

• Array
• Backtracking

相似题目

• Next Permutation 中等
• Permutations II 中等
• Permutation Sequence 困难
• Combinations 中等

build graph

O(n! * n)

复杂度

• 时间复杂度：O(P(n, k))
  • K~[0,n]
  • 对于每一位，可以从n个元素中选择k个来放置，共有n位。
• 空间复杂度 O(n!)
  • 共有N!个全排列，故需要保存N!个解

1.DFS-Permutation-Recursion

This recursion/backtracking is already stack data structure.

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []

        allpermutations = []
        self.dfs(nums, [], set(), allpermutations)
        return allpermutations
    
    # 递归的定义： 找到所有curr_permutation开头的permutations
    def dfs(self, nums, curr_permutation, visited, allpermutations):
        if len(curr_permutation) == len(nums):
            allpermutations.append(list(curr_permutation)) # deep copy
            return 

        for num in nums:
            if num in visited:
                continue # add other nums except itself
            # add other nums
            curr_permutation.append(num)
            visited.add(num)
            self.dfs(nums, curr_permutation, visited, allpermutations)
            # remove added nums. backtracking
            curr_permutation.remove(num)
            visited.remove(num)

java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> allpermutations = new ArrayList<>();
        if (nums == null || nums.length == 0){
            return allpermutations;
        }

        Set<Integer> visited = new HashSet<>();
        ArrayList<Integer> currPermutation = new ArrayList<>();
        this.dfs(nums, currPermutation, allpermutations, visited);
        return allpermutations;
    }

    // recursion definition: find all permutations starting with currPermutation
    private void dfs(int[] nums, 
                     ArrayList<Integer> currPermutation, 
                     List<List<Integer>> allpermutations,
                     Set<Integer> visited){
        // recursion stopping
        if (currPermutation.size() == nums.length){
            allpermutations.add(new ArrayList<Integer>(currPermutation));
            return;
        }

        // recursion divide
        // [] -> [1] [2] [3] ...
        // [1] -> [1,2] [1,3] ...
        for (int i = 0; i < nums.length; i++){
            if (visited.contains(nums[i])){
                continue;
            }
            currPermutation.add(nums[i]);
            visited.add(nums[i]);
            this.dfs(nums, currPermutation, allpermutations, visited);
            currPermutation.remove(currPermutation.size() - 1); // backtracking
            visited.remove(nums[i]); // backtracking
        }

    }
}

2.Non-Recursion 有点复杂 容易出错 不推荐

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []

        stack = collections.deque([-1]) # store index
        permutation = [] # store corresponding value
        permutations = [] 

        while len(stack):
            index = stack.pop()
            index += 1
            while index < len(nums):
                if nums[index] not in permutation:
                    print(1111)
                    break # break until first element which is not visited (in stack)
                index += 1
            else: # when index == len(nums) (after pushing all elements into stack)
                if len(permutation):
                    permutation.pop() 
                continue # continue the while len(stack). This 

            # every time stack add element, also add into permutation
            stack.append(index) # push real indexes
            stack.append(-1) # prep for next stack.pop()
            permutation.append(nums[index])
            if len(permutation) == len(nums):
                permutations.append(list(permutation))
        return permutations