RECUR22 - Editorial

Problem Link - All Possible Subsets in Recursion

Problem Statement:

You are given an Array and you have to output all possible subsets of that array.
You have to print the subarrays in sorted order.

Approach:

  • Recursive Function: The allPossibleSubsets function takes the current index, the original array, the current subset being built, and a reference to all subsets found so far.
  • Base Case: If the index reaches the size of the array, the current subset is added to the list of all subsets.
  • Recursive Cases:
    • First, it explores the case where the current element is not included.
    • Then, it includes the current element in the subset and recursively explores further.
    • After including the element, it backtracks by removing the last added element to ensure the next iteration starts with the correct state.
  • Backtracking: The use of backtracking ensures that we explore all combinations without skipping any potential subsets.
  • Sorting: After generating all subsets, we sort them to maintain the required order in the output.

Complexity:

  • Time complexity: The time complexity is O(2^N) because there are 2^N possible subsets for an array of size N. Each subset takes O(N) time to copy into the result.
  • Space Complexity: The space complexity is O(N) for the recursive call stack at maximum depth and O(2^N) for storing the subsets in the result. Thus, the overall space complexity is O(N+2^N).