Subsets

LeetCode 78 · View on LeetCode

Backtracking: at each index, choose to include or exclude the current element. Build the subset incrementally and backtrack after each recursive call.

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    def backtrack(start: int, path: list[int]):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

if __name__ == '__main__':
    print(subsets([1, 2, 3]))
    # [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

    print(subsets([0]))
    # [[], [0]]