废话不说，直接看题:
题目非常简单，给定一个distinct的列表，求它的power set。
先说一些题外话，这个函数实际上应用非常广，比如在machine learning中，如果我们需要做feature selection，就是从feature universe里面选出一个子集来提高validation set的准确率，我们就需要这个函数生成feature power set。当然这样做的复杂度比较高，是
所以我翻看了一下我的ML的课堂笔记，看看老师是怎么实现这个函数的:
def subsets(features):
if len(features) == 0:
return []
cs = subsets(features[1:])
return [[features[0],]] + [[features[0],]+ c for c in cs]+ cs
哈哈，乍一看根本不知道写的是个啥，不急，我们先来对python的基本语法做一些说明：
- list的相加：python的语法里面是可以进行list的加法运算的，其效果就是把两个list的元素合并为一个list. e.g: [3]+[5]=[3,5]; []+[3]=[3];
3+[5]=error!
所以直观上来看这个函数显而易见，首先cs求出这个列表第2至n项所生成的power set，再把第一个元素加上就行了，[[features[0]]]表示第一个元素生成的subset，[[features[0],]+ c for c in cs]表示第一个元素与cs合并生成的子集，cs表示剔除第一个元素后，别的元素生成的子集。
但是上面的代码有一点问题，他忽略的空集，修改后的代码如下所示：
def subsets(features):
if len(features) == 0:
return [[]]
cs = subsets(features[1:])
return [[features[0]]+ c for c in cs]+ cs
当然上面那个代码也是有实际意义的，因为在machine learning中我们是不会对空集进行测试的。
先提纲挈领的说一下，这种题目在面试中经常考，与之相关的有排列，组合等问题，他们自身的复杂度本身就是指数级别的，所以不能从时间复杂度上进行优化，一般出这种题目是考察你的算法能力。解决这种题递归(recursion)和回溯(backtracking)是最常用的方法。下面对一些变形进行一些说明
2.上面题目不变，请选择出长度为k的子集(Two sigma onsite)
这个题是一道典型的组合问题，组合问题一般地解法就是回溯法(backtrack)。废话不说，先看答案
def subsets(nums):
def backtrack(first = 0, curr = []):
# if the combination is done
if len(curr) == k:
output.append(curr[:])
for i in range(first, n):
# add nums[i] into the current combination
curr.append(nums[i])
# use next integers to complete the combination
backtrack(i + 1, curr)
# backtrack
curr.pop()
output = []
n = len(nums)
for m in range(k,k + 1):
backtrack()
return output
回溯法的基本做法就是一个递归函数，一个判断是否为可行解，在这里可行解的判断条件是长度是否为k.实话说，递归函数看的人眼花缭乱，这里我们的做法就是从全局来看，比方说
if len(curr) == k:
output.append(curr[:])
这个代码就是判断解是否满足条件，如果满足条件就把他放到最终的解空间里面。
for i in range(first, n):
# add nums[i] into the current combination
curr.append(nums[i])
# use next integers to complete the combination
backtrack(i + 1, curr)
# backtrack
curr.pop()
这个是回溯函数的主体，第一行curr.append(nums[i])是把一个新元素放到列表里面，backtrack(i + 1, curr)是把从第i+1个到最后一个元素与第一个元素结合生成的所有可行解，curr.pop()将第一个元素剔除，然后进入下一个循环(因为以第一个元素构成的排列已经枚举完了)
3.排列问题(Permutation)
Given a list composed of distinct integers, generate its all permutations.
这个题使用递归就可以完美解决，下面先看答案
def permute(nums):
if len(nums) == 1:
return [nums]
result = []
for i in range(len(nums)):
nums[0], nums[i] = nums[i], nums[0]
B = self.permute(nums[1:])
result = result+[ele+[nums[0]] for ele in B]
return result本质和组合一样，也是使用递归。唯一的区别是因为排列是有顺序的，所以第一个元素可以由很多元素来担当，所以这个循环很关键，来让所有元素都当首元素。
Yang Gao 