难度: Medium
某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。
返回结果 无顺序要求，但不能含有重复的元素。
示例 1:
输入：goods = "agew" 输出：["aegw","aewg","agew","agwe","aweg","awge","eagw","eawg","egaw","egwa","ewag","ewga","gaew","gawe","geaw","gewa","gwae","gwea","waeg","wage","weag","wega","wgae","wgea"]
提示：
1 <= goods.length <= 8运行时间: 200 ms
内存: 19.3 MB
class Solution:
def permutation(self, s: str) -> List[str]:
result = []
s = sorted(s)
def backtrack(path):
if len(path) == len(s):
result.append(''.join(path))
for i in range(len(s)):
if s[i] is None:
continue
if i > 0 and s[i] == s[i-1]:
continue
path.append(s[i])
s[i] = None
backtrack(path)
s[i] = path.pop()
backtrack([])
return result
这个题解使用了回溯法（Backtracking）来找出字符串的所有排列组合。首先，对输入字符串进行排序，以便于后续去重操作。回溯函数backtrack考虑了当前构建的排列（path），如果path的长度与输入字符串长度相同，说明找到了一个完整的排列，将其加入结果列表。在每一步递归中，循环遍历字符串的每个字符，对于已经使用过的字符通过将其设为None来标记。同时，为了避免在递归中产生重复的排列，如果当前字符与前一个字符相同，并且前一个字符已经被使用过，则跳过当前字符。在递归调用后，需要撤销之前的操作（即回溯），通过将字符从path中移除并恢复其在字符串中的位置。
时间复杂度: O(n * n!)
空间复杂度: O(n * n!)
class Solution:
def permutation(self, s: str) -> List[str]:
result = []
s = sorted(s) # 排序以便去重
def backtrack(path):
if len(path) == len(s):
result.append(''.join(path)) # 当路径长度等于s长度时，找到一个解
for i in range(len(s)):
if s[i] is None: # 跳过已经使用的字符
continue
if i > 0 and s[i] == s[i-1]: # 跳过重复字符
continue
path.append(s[i]) # 选择当前字符
s[i] = None # 标记当前字符为已使用
backtrack(path) # 递归调用
s[i] = path.pop() # 撤销选择，回溯
backtrack([])
return result
排序字符串使得相同的字符相邻，这样在遍历和生成排列的过程中，可以容易地识别并跳过重复的字符，从而避免生成重复的排列。当递归生成排列时，如果发现当前字符与前一个字符相同，并且前一个字符已经被处理过（即在同一层递归中考虑过），就可以跳过当前字符，因为继续使用会生成与之前相同的排列，导致重复。
这种做法确保不会遗漏任何有效的排列组合是基于对字符串排序的前提下实现的。在排序的字符串中，相同的字符是连续的。在生成排列的过程中，我们确保每个字符在每个可能的位置只被考虑一次。当我们遇到一个重复的字符时，如果它的相同前一个字符还未被使用过，意味着之前在这个递归层级已经考虑过这种字符的配置，因此跳过当前字符不会遗漏任何组合，只是避免重复生成相同的排列。