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 are2^N
possible subsets for an array of sizeN
. Each subset takesO(N)
time to copy into the result. - Space Complexity: The space complexity is
O(N)
for the recursive call stack at maximum depth andO(2^N)
for storing the subsets in the result. Thus, the overall space complexity isO(N+2^N)
.