Leetcode题78、子集（Python题解）字节跳动面试题

问题：

题目来源：力扣（LeetCode）

leetcode78.子集

难度：中等

分析： 回溯法。 子集问题相当于记录组合问题的每一步结果，在组合问题上稍加改动即可。 建议刷题顺序：排列–组合–子集 此外还有基于python技巧的解法，和非常优美的基于子集生成规律的写法 解决方法： 1：回溯法

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: if nums == []: return [[]] def backtrack(idx): #不需要等一条路径回溯结束再保存值，每一步都要保存值。 ans.append(path[:]) for i in range(idx, len(nums)): path.append(nums[i]) backtrack(i+1) path.pop() path = [] res = [] backtrack(0) return res

还有一种带参回溯的写法。

#回溯的另一种写法，因为再回溯的时候将每一层的结果都传递下去了，相当于每一层重写赋值path， #因此不向回撤也可以，相当于自动回撤，这对于空间的占用较高。 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def helper(index, path): res.append(path) #把上层结果添加到res里 #print(tmp) for i in range(index, len(nums)): helper(i + 1, path + [nums[i]]) #向下递归，并把本层结果传递到下一层 res = [] helper(0, []) return res

2：python技巧

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] for i in range(len(nums)+1): for tmp in itertools.combinations(nums, i): res.append(tmp) return res

3：迭代方法，非常优美

#这个写法太python了，优美！ #新元素增加的新的组合，就是前面元素所有的组合再加上这个元素，再将新元素增加的组合融合进组合总体中，进入下一轮循环。 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [[]] for i in nums: res = res + [[i] + num for num in res] return res