38. 字符串的排列

时间：2020-03-28 12:25:03 收藏：0 阅读：44

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

示例:

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

思路：本问题可以利用回溯法的思想解决。
我们不知道它明确的计算法则。而是先进行试探，试探到最终状况，发现不满足问题的要求，则回溯到上一个状态继续试探。
这种不断试探和回溯的思想，称为回溯法（Backtrcking）。

class Solution: 
    def permutation(self, s: str) -> List[str]:
        length = len(s)
        if length == 1: return [s] # 边界
        else:
            res = []
            for i in range(length):
                ch = s[i]   #取出s中每一个字符
                rest = s[:i] + s[i+1:]
                for x in self.permutation(rest): #递归
                    res.append(ch + x)  #将ch 和子问题的解依次组合
        return list(set(res))

class Solution: 
    def permutation(self, nums: List[int]) -> List[List[int]]:
        res=[]
        nums = sorted(nums)
        def helper(nums,temp):
            if not nums:
                res.append(temp)
            for i in range(len(nums)):
                if i>0 and nums[i]==nums[i-1]:
                    continue
                helper(nums[:i]+nums[i+1:],temp+[nums[i]])
        helper(nums,[])
        return res

参考博客:https://blog.csdn.net/summer_dew/article/details/83921581

原文：https://www.cnblogs.com/USTC-ZCC/p/12586402.html