78.子集--77.组合

78，子集

递归

class Solution(object):def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""# 结果ans=[]# 临时结果dp_=[]def dfs(nums,index):if index==len(nums):# 保存结果co_dp=dp_[:]ans.append(co_dp)return # 终止条件# 不选：dfs(nums,index+1)# 选dp_.append(nums[index])dfs(nums,index+1)dp_.pop()dfs(nums,0)return ans

77.组合

递归  没有优化

class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""# 结果ans=[]# 临时结果dp_=[]def dfs(index,k):if index==n+1:                # 保存结果# 加一个判断len(dp_==k)if len(dp_)==k:co_dp=dp_[:]ans.append(co_dp)return # 终止条件# 不选：dfs(index+1,k)# 选dp_.append(index)dfs(index+1,k)dp_.pop()dfs(1,k)return ans

优化后

class Solution(object):def combine(self, n, k):""":type n: int:type k: int:rtype: List[List[int]]"""# 结果ans=[]# 临时结果dp_=[]def dfs(index,k):# 提前判断终止if len(dp_)>k or len(dp_)+n-index+1<k:returnif index==n+1:                # 保存结果# 加一个判断len(dp_==k)# if len(dp_)==k:co_dp=dp_[:]ans.append(co_dp)return # 终止条件# 不选：dfs(index+1,k)# 选dp_.append(index)dfs(index+1,k)dp_.pop()dfs(1,k)return ans