子集

Leetcode Link: 78. 子集 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

解法一

思路：自己想的，相当于一个树的遍历，

满足题目条件：只要节点能被访问到，就是满足条件的

终止回溯的条件：choose 为空

新的choose总是在上一次choose中选择的值的后面的所有的值组成的。即不往前看，只往后看。

题解：

class Solution:
    # 满足条件：所有节点
    # 终止回溯：choose为空
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtracking(choose):
            nonlocal res, path
 
            # 每次访问一个节点就可以添加到 res
            # 这个如果放到停止回溯的后面会丢失情况
            res.append(copy.deepcopy(path))
            # 停止回溯
            if choose == []:
                return
 
            for idx, val in enumerate(choose):
                path.append(val)
                backtracking(choose[idx+1:])
                path.pop()
 
        res = []
        path = []
        backtracking(nums)
        return res

启发和联系