← Back to Portfolio

Recursion / Backtracking

Subsets

Generate all possible subsets of a given array using recursion and backtracking.

Intuition

For every element we have two choices: either include it in the subset or exclude it. This naturally forms a recursion tree.

Algorithm

  1. Start recursion from index 0
  2. Include current element
  3. Move to next index
  4. Backtrack by removing element
  5. Exclude current element

Dry Run

[]
[1]
[1,2]
[2]

Python Solution 



class Solution:

    def subsets(self, nums):

        ans = []

        def backtrack(i, curr):

            if i == len(nums):

                ans.append(curr[:])
                return

            curr.append(nums[i])

            backtrack(i + 1, curr)

            curr.pop()

            backtrack(i + 1, curr)

        backtrack(0, [])

        return ans