1. 子集（leetcode 第78题）
# 在原子集的基础上添加元素，扩充到result里面 Slicing的方式 def subsets(nums): result = [[]] for num in nums: for element in result[:]: # slicing 相当于make copy ,这里为什么要make copy呢，直接result不行吗？不行，随着result不断增加元素，会进入无限死循环 x = element[:] # 这里为什么会加slicing?因为不make copy的话，会修改掉原来的element，导致原子集消失 x.append(num) result.append(x) return result
方法二：回溯算法
def subsets_recursive(nums): lst = [] result = [] subsets_recursive_helper(result, lst, nums, 0) return result; def subsets_recursive_helper(result, lst, nums, pos): result.append(lst[:]) # 添加路径 子集问题需要在每个节点收集结果。 for i in range(pos, len(nums)): # 从选择列表里面挑选 lst.append(nums[i]) # 做选择 subsets_recursive_helper(result, lst, nums, i+1) # 回溯 lst.pop() # 撤销选择
2. 子集Ⅱ（leetcode 第90题）
# 第一种解法 def subsets2(nums): res = [[]] for num in nums: res += [ i + [num] for i in res if i + [num] not in res] return res # 第二种解法 def subsets_recursive2(nums): lst = [] result = [] nums.sort() # 先sort一下，以便于做比较 print(nums) subsets2_recursive_helper(result, lst, nums, 0); return result def subsets2_recursive_helper(result, lst, nums, pos): result.append(lst[:]) for i in range(pos, len(nums)): if (i > pos and nums[i] == nums[i-1]): # 就在这里添加这一个限制条件即可 continue lst.append(nums[i]) subsets2_recursive_helper(result, lst, nums, i+1) lst.pop()
3. 排列（leetcode 面试题 08.07. 无重复字符串的排列组合）
def perm(nums): res = [] perm_helper(res, nums) def perm_helper(res, nums): if (len(nums)==0): # 结束条件 这里并不需要像前几个题一样每个节点都需要加进去，只需要添加叶子节点即可 print("".join(res)) for i in range(len(nums)): res.append(str(nums[i])) perm_helper(res, nums[0:i]+nums[i+1:]) # 将当前节点从选择列表中删除 res.pop()