Subsets | Leetcode 78 | GFG | C++ Solution with intuition and code | DSA Recursion and Backtracking

In this video I have solved this question i.e. subsets which is based on recursion & backtracking concept.
Intuition behind this problem is that for generating all possible subsets you have explore all possible options and at every index you have 2 choice either to pick this element or not pick.
The function takes four parameters:
index: the current index in the input array.
a: the input array of integers.
ans: a temporary vector that stores the current subset being constructed.
result: a vector of vectors that stores all the subsets generated.
Base Case:
When index is equal to or greater than the size of the input array, it means we have considered all elements. The current subset (ans) is then added to the result.
Recursive Steps:
Pick the current element: The current element at index is added to the ans vector, and the function is called recursively for the next index (index + 1).
Backtrack: After returning from the recursive call, the last element is removed from ans (backtracking).
Not Pick the current element: The function is called again for the next index without including the current element.
Sorry for the TC mistake in the video.
TC: The Time Complexity is O(n*2^n) where n is the number of elements in the input array. This is because as each element has two choices: To be included in the subset or not. Therefore, there are 2^n possible subsets. And each subsets take on an avg O(n) time to copy the ans into result. SO overall TC becomes O(n*2^n) Sorting TC is also counted but overall is has no impact so we take only O(n*2^n)
SC: The space complexity for the code is O(2^n * L) + O(N) where L is the length of each subsets. And O(N) for the recursion stack
Here we are not considering the ans and result vector space as they were needed to solve this question demanded by the question only.
#datastructure #leetcode #datastructuresandalgorithmsinpython #computerscience #programming #leetcodeproblems #leetcodedailychallenge #gfg #gfgstreek #gfgpotd #gfgsolutions #dsa #btech #btechjobs #btechprojects #datastructuresandalgorithms