#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/backtracking/subsets-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/backtracking/subsets-implementation

Repovive

Subsets - Implementation - Backtracking | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Subsets - Implementation

Here is the implementation:

function subsets(nums):
    result = []
    backtrack(0, [])
    return result

function backtrack(index, current):
    if index == nums.length:
        result.append(copy of current)
        return

    // Include nums[index]
    current.append(nums[index])
    backtrack(index + 1, current)
    current.pop()

    // Exclude nums[index]
    backtrack(index + 1, current)

$O(n \cdot 2^n)$ time to generate all subsets and copy them. $O(n)$ space for recursion stack.