回溯——子集（python）

思路：

将树型结构画出来理解。对于一个数，可以选或者不选，这是关键。当到达最后一个位置时，也就是到达树型结构最底层时，收集答案。

关键点：

对于一个数，可以选或者不选

path.append(nums[i]) #选择该数

dfs(pos+1) #带着选好的数，递归到下一层

path.pop() #不选该数

dfs(pos+1) #不选该数，递归到下一层

import sys from typing import List def subsets(nums:List[int])->List[List[int]]: res=[] path=[] n=len(nums) def dfs(pos): nonlocal res if pos==n: #收集答案 res.append(path[:]) return path.append(nums[pos]) #选择该数字 dfs(pos+1) #带着这个数，进入下一层递归 path.pop() #不选择该数字 dfs(pos+1) #不带该数字，进入下一次递归 dfs(0) print(res) return def main(): line=sys.stdin.readline().strip() if not line: return nums=list(map(int,line.split())) subsets(nums) if __name__=="__main__": main()