全排列问题可以套用模版：DFS找出所有符合要求的情况

1. lc 46 - 全排列

  • 题目来源
  • 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
  • 难度：中等

解题思路

直接看代码， 此题可以作为此类题模版了。

复杂度

  • 时间复杂度：O(n*n!)
  • 空间复杂度：O(n) 其中 n 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 o(n)

具体请看：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0: return []

        self.res = []
        self.length = len(nums)
        self.recursion([],nums)
        return self.res
        
    '''
    choosen列表储存一种新的排列的元素
    candidates列表存储待选的元素
    '''
    def recursion(self,choosen,candidates):
        if len(choosen) == self.length: # 当 choosen 长度达到要求，加入返回列表res中
            self.res.append(choosen)  
            return
        for i in range(len(candidates)): # 遍历 candidates列表 每个待选，放入到choosen，递归直到产生一种新的排序
            tmp1 = choosen.copy() # 注意：需要对原数组拷贝，否则直接操作会改动到原数组
            tmp1.append(candidates[i])

            tmp2 = candidates.copy() 
            del (tmp2[i])

            self.recursion(tmp1,tmp2)

类似题：剑指 38 - 字符串的排列

与上题区别：对象为字符串。字符串会存在重复字符。需要剪枝操作，排除重复方案。需在固定某位字符时，保证 “每种字符只在此位固定一次” ，即遇到重复字符时不交换，直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。

Question source

解题思路

套用模版，但需要剪枝操作，否则超时。可使用哈希表判重。

复杂度

  • 时间复杂度：递归树的中间节点 O(N!), 然后每个中间节点内部有一个for循环，那么合计为 O(N * N!)。
  • 空间复杂度： O(n^2) ,全排列的递归深度为 N ，系统累计使用栈空间大小为 O(N) ；递归中辅助 Set 累计存储的字符数量最多为 N+(N−1)+...+2+1=(N+1)^N/2 ，即占用 O(N^2) 的额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permutation(self, s: str) -> List[str]:
        self.res = []
        self.s = s
        self.recursion(s,"")
        return self.res

    def recursion(self,candidates,choosen):
        hashmap = dict() # 额外空间用于剪枝

        if len(choosen) == len(self.s) :
            self.res.append(choosen)
            return
        for i in range(len(candidates)):
            if candidates[i] in hashmap.keys():
                continue
            else:
                hashmap[candidates[i]] = 0
            self.recursion(candidates[:i]+candidates[i+1:], choosen+candidates[i])