典型的对带重复元素的输入进行全排列计算的问题，基于回溯算法解决。

Question

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

1 2	`输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]`

限制：1 <= s 的长度 <= 8

测试用例

功能测试（输入的字符串中有一个或者多个字符）。特殊输入测试（输入的字符串的内容为空或者 nullpt r指针）。

本题考点

考查应聘者的思维能力。当整个问题看起来不能直接解决的时候，应聘者能否想到把字符串分成两部分，从而把大问题分解成小问题来解决，是能否顺利解决这个问题的关键。考查应聘者对递归的理解和编程能力。

Intuition

典型的对带重复元素的输入进行全排列计算的问题，基于回溯算法进行解决。

Code

class Solution:
    def permutation(self, s: str) -> List[str]:
        """
        :param nums: List[int]
        :param m: int   
        :return: List[List[int]]
        """
        nums = list(s)
        if not nums: return []
        res = []
        n = len(nums)
        
        def backtrack(nums, path, depth):
            """backtrack based on the digging out select number
            :param nums: List[int]
            :param path: List[int]
            :param depth: depth
            :return: None
            """
            if depth == n:
                tmp =  ''.join(path[:])
                if tmp not in res:
                    res.append(tmp)
            # if depth == n:  res.append()
            # 以range(len(nums))作为选择列表，则之前那个已经被挖掉的元素不会再被选择
            for i in range(len(nums)):
                # 递归调用时就挖掉了那个已经选择的元素
                backtrack(nums[:i]+nums[i+1:], path+[nums[i]], depth+1)
        
        backtrack(nums, [], 0)
        return res

# output
----------------------------------------------------------------------
Ran 1 test in 4.160s
OK

另一种实现去重的全排列算法，在过程中剪枝，速度更快。

class Solution:
    def permutation(self, s: str) -> List[str]:
        """permutation with repeatable input
        :param nums: List[int]
        :return: List[List[int]]
        """
        nums = list(s)
        if not nums: return []
        # if not nums:  return
        res = []
        n = len(nums)
        visited = [False] * n

        def backtrack(path, depth):
            """backtrack based on extra space visted vector
            :param path: List[int]
            :param depth: int
            :return: None
            """
            if depth == n:  res.append(''.join(path[:]))
            for i in range(n):
                if visited[i]:  continue
                # 就加了这一句剪枝，那为什么要求visited[index-1]必须为False？
                # 因为一般回溯到这里时，前面visited[index-1]的占用可能没有被撤销。
                # 所以要对 visited[index-1] 处进行检查。
                if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:  continue
                visited[i] = True
                backtrack(path+[nums[i]], depth+1)
                visited[i] = False

        # 由于要剪枝，所以必须要提前对nums进行排序，让重复的数字排列在一起。
        nums.sort() 
        backtrack([], 0)
        return res

# output
----------------------------------------------------------------------
Ran 1 test in 0.142s
OK

测试单元

import unittest
from typing import List

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution1()

    def test_solution(self):
        words = [
            "ryawrowv",               # 功能测试
                                      # 边界值的测试
            ""                        # 特殊样例
        ]
        answers = [10080, 0]
        res = []
        for i in range(len(words)):
            res.append(len(self.test_class.permutation(words[i])))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class

if __name__ == "__main__":
    unittest.main()

Extension

如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？还是输入三个字符a、b、c，则它们的组合有a、b、c、ab、ac、bc、abc。当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。比如ab和ba是不同的排列，但只算一个组合。如果输入n个字符，则这n个字符能构成长度为1，2…，n的组合。在求n个字符的长度为 m(1≤m≤n) 的组合的时候，我们把这n个字符分成两部分：第一个字符和其余的所有字符。如果组合里包含第一个字符，则下一步在剩余的所有字符里选取m-1个字符；如果组合里不包含第一个字符，则下一步在剩余的n-1个字符里选取m个字符。也就是说，我们可以把求n个字符组成长度为m的组合的问题分解成两个子问题，分别求n-1个字符中长度为m-1的组合，以及求n-1个字符中长度为m的组合。这两个子问题都可以用递归的方式解决。

相关题目

八皇后问题
摆数字输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点上（如图所示），使得正方体上三组相对的面上的4个顶点的和都相等。这相当于先得到 \(a_1\)、\(a_2\)、\(a_3\)、\(a_4\)、\(a_5\)、\(a_6\)、\(a_7\) 和 \(a_8\) 这8个数字的所有排列，然后判断有没有某一个排列符合题目给定的条件，即 \(a_1 + a_2 + a_3 + a_4 = a_5 + a_6 + a_7 + a_8\)，并且 \(a_1 + a_2 + a_5 + a_6 = a_3 + a_4 + a_7 + a_8\) 。

举一反三 如果面试题是按照一定要求摆放若干个数字，则可以先求出这些数字的所有排列，然后一一判断每个排列是不是满足题目给定的要求。

总结

在面试时，我们难免会遇到难题，画图、举例和分解这3种方法能够帮助我们解决复杂的问题。 图形能使抽象的问题形象化。当面试题涉及链表、二叉树等数据结构时，如果在纸上画几张草图，则题目中隐藏的规律就有可能变得很直观。 一两个例子能使抽象的问题具体化。很多与算法相关的问题都很抽象，未必一眼就能看出它们的规律。这时候我们不妨举几个例子，一步一步模拟运行的过程，说不定就能发现其中的规律，从而找到解决问题的窍门。 把复杂问题分解成若干个小问题，是解决很多复杂问题的有效方法。如果我们遇到的问题很大，则可以尝试先把大问题分解成小问题，然后再递归地解决这些小问题。分治法、动态规划等方法应用的都是分解复杂问题的思路。

剑指offer

回溯算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

剑指offer 面试题39. 数组中出现次数超过一半的数字（易）& LeetCode 169. 多数元素（易）上一篇

面试题37. 序列化二叉树（难）& LeetCode 297. 二叉树的序列化与反序列化（难）下一篇

剑指offer 面试题38. 字符串的排列（中）

Question

Intuition

Code

Extension