189 8069 5689
# -*- coding: utf-8 -*-
# @Time : 2019-07-08 9:52
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : stringCombination.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
排列组合一般都可通过递归来解决。
先确定递归出口：当找到了一个既定长度的组合或者剩余的字符不足以凑成既定长度的组合就该结束该层递归
然后确定如何递归：长度为n的字符串的组合的长度在1到n之间，而对于长度为m的其中一个组合，若在给定
字符中第一个字符不选，那么需要从剩余的n-1个字符中选择m个字符；
若选择第一个字符，那么需要从剩余的n-1个字符中选择m-1个字符。
注意两种选择是互斥的，因此在结束一种选择之后需要确保还原状态
"""
def Combination(self, ss):
"""
对给定字符串进行全排列
:param ss: 带排列字符串
:return: 一个列表，包含所有可能的排列，其中元素顺序符合字典序
"""
def helper(s, length):
# 如果剩余位数为0，那么代表既定长度的字符串组合已经找到，添加到结果中
if length == 0:
ans.add(''.join(temp))
# 如果剩余的可选字符为0，那么结束
elif not s:
return
else:
# 否则，先将第一个字符加入temp列表中，然后从剩余字符中选length-1个
temp.append(s[0])
helper(s[1:], length - 1)
# 或者，第一个字符不选，从剩余字符中选length个。那么就先要将第一个字符从temp
# 列表中剔除
temp.pop(-1)
helper(s[1:], length)
if not ss:
return []
ans = set()
temp = []
for i in range(1, len(ss) + 1):
helper(list(ss), i)
return sorted(list(ans), key=lambda x: (len(x), x))
def main():
s = "abc"
solution = Solution()
ans = solution.Combination(s)
print(ans)
if __name__ == '__main__':
main()
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
