Find all subsequence combinations of a string (Memoization)

Given a string 'abc', find all distinct subsequence combinations of it.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find all subsequence combinations of a string, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = {}

def combine(s):
  if len(s) == 0:
    return []

  global cache

  if s[:-1] not in cache:
    l = combine(s[:-1])
    cache[s[:-1]] = l + [x + s[-1] for x in l] + [s[-1]]

  return cache[s[:-1]]

s = 'abc'

print(combine(s))

const cache = {}

function combine(s) {
  if (s.length === 0) {
    return [];
  }

  if (cache[s.slice(0, -1)] === undefined) {
    const l = combine(s.slice(0, -1));
    cache[s.slice(0, -1)] = [...l, ...l.map(x => x + s.slice(-1)), s.slice(-1)];
  }
  
  return cache[s.slice(0, -1)];
}

const str = 'abc';

console.log(combine(str));