2.10 Backtracking

LC 78. Subsets §

Explanation

• This is how it works

Python

# Time complexity: O(n*2^n)
 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        all_subsets = []
        
        def backtrack(start, current_subset):
            all_subsets.append(current_subset.copy())
            
            for i in range(start, len(nums)):
                # Include the number at the current index
                current_subset.append(nums[i])
                # Recurse on the remaining elements
                backtrack(i + 1, current_subset)
                # Exclude the number at the current index
                current_subset.pop()
        
        backtrack(0, [])
        return all_subsets
 

C++

// Time complexity: