Power Set

Print all the possible subsequences of the String

Recursion + Backtracking

On each step we have two options
take or not take

Once we reach the end of index,
we append the curr_string to res
and break the recursion

TC: O(2^n)
SC: O(n) ~> Recursion stack

Solution

def all_substrings(s):
    res, n = [], len(s)

    def recurse(ind, curr_str):
        if ind == n:
            res.append(curr_str)
            return

        recurse(ind+1, curr_str + s[ind])
        recurse(ind+1, curr_str)
    
    recurse(0, "")
    return sorted(res)