DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Subsets - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtrack(idx, subset):
            if idx >= len(nums):
                res.append(subset.copy())
                return
                
            # Include the current element
            subset.append(nums[idx])    # Choose
            backtrack(idx + 1, subset)  # Explore
            subset.pop()                # Undo (Backtrack)

            # Exclude the current element
            backtrack(idx + 1, subset)
        
        backtrack(0, [])
        return res

Complexity Analysis

Here, n is the input size, and there are 2ⁿ total subsets for n elements.

  • Time Complexity: O(n * 2ⁿ)

    • At every index, we make two recursive calls (include and exclude), leading to 2ⁿ recursive paths. At each base case (leaf), we make a copy of the current subset, which can take up to O(n) time.
      So total time = time to copy each subset × number of subsets = O(n * 2ⁿ).

  • Space Complexity: O(n * 2ⁿ)

    • O(n * 2ⁿ) space is needed to store all subsets in the result list (Dominates the space complexity).
    • O(n) auxiliary space is used for the recursion call stack and current subset list during the backtracking process.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtrack(idx, subset):
            if idx >= len(nums):
                res.append(subset.copy())
                return
            
            # Exclude the current element
            backtrack(idx + 1, subset)

            # Include the current element
            subset.append(nums[idx])
            backtrack(idx + 1, subset)
            
            # Backtrack: Undo the include decision (Important step)
            subset.pop()
            
        backtrack(0, [])
        return res

Complexity Analysis

Here, n is the input size, and there are 2ⁿ total subsets for n elements.

  • Time Complexity: O(n * 2ⁿ)

    • At every index, we make two recursive calls (include and exclude), leading to 2ⁿ recursive paths. And for each subset, we do up to O(n) work. So total time = time to copy each subset × number of subsets = O(n * 2ⁿ).

  • Space Complexity: O(n * 2ⁿ)

    • O(n * 2ⁿ) total for storing all subsets.
    • And O(n) auxiliary space is used for the call stack and current subset during recursion.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        
        def backtrack(idx):
            if idx >= len(nums):
                res.append(subset.copy())
                return

            # Include
            subset.append(nums[idx])    # Choose
            backtrack(idx + 1)          # Explore
            subset.pop()                # Undo (Backtrack)

            # Exclude
            backtrack(idx + 1)
        
        backtrack(0)
        return res

Complexity Analysis

Here, n is the input size, and there are 2ⁿ total subsets for n elements.

  • Time Complexity: O(n * 2ⁿ)

    • Two recursive calls at each index (include and exclude), giving 2ⁿ paths, and each subset is copied at the base case which is O(n) work. So total time = time to copy each subset × number of subsets = O(n * 2ⁿ).

  • Space Complexity: O(n * 2ⁿ)

    • O(n * 2ⁿ) total for storing all subsets.
    • O(n) extra space for the recursion call stack and mutable subset list.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        
        def backtrack(cur_idx, cur_subset):
            # Append a copy of current subset
            res.append(cur_subset.copy())

            # Iterate through the remaining elements
            for idx in range(cur_idx, len(nums)):
                cur_subset.append(nums[idx])        # Choose
                backtrack(idx + 1, cur_subset)      # Explore
                cur_subset.pop()                    # Undo

        backtrack(0, [])
        return res

Complexity Analysis

Here, n is the input size, and there are 2ⁿ total subsets for n elements.

  • Time Complexity: O(n * 2ⁿ)

    • The loop recursively explores all combinations starting from each index. There are 2ⁿ subsets generated, so the number of recursive calls is still 2ⁿ. And each copy of a subset takes up to O(n) time. So total time = time to copy each subset × number of subsets = O(n * 2ⁿ).

  • Space Complexity: O(n * 2ⁿ)

    • Result Space: There are 2ⁿ subsets, and each subset can have up to n elements. So the total output size O(n * 2ⁿ).
    • Auxiliary Space: O(n) extra space for the recursion call stack. No shared list, so each recursive call creates a new list up to size n, and these are short-lived.

    Overall auxiliary space is higher than the reuse version due to many new list objects being created, but asymptotically still the total space is O(n × 2ⁿ).

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        
        def backtrack(cur_idx):
            # Append a copy of current subset
            res.append(subset.copy())

            # Iterate through the remaining elements
            for idx in range(cur_idx, len(nums)):
                subset.append(nums[idx])    # Choose
                backtrack(idx + 1)          # Explore
                subset.pop()                # Undo

        backtrack(0)
        return res

Complexity Analysis

Here, n is the input size, and there are 2ⁿ total subsets for n elements.

  • Time Complexity: O(n * 2ⁿ)

    • The recursive tree has branching from every index current index to the last index, but in total it explores all subsets. There are 2ⁿ subsets generated, so the number of recursive calls is still 2ⁿ. And each copy of a subset takes up to O(n) time.
      So total time = time to copy each subset * number of subsets = O(n * 2ⁿ).

  • Space Complexity: O(n * 2ⁿ)

    • O(n × 2ⁿ) space for the result (Dominates the space complexity).
    • O(n) auxiliary space is used for the recursion stack and current shared subset.