class Solution:
  def generateGeneralizedAbbreviation(self, word):
    
    # converts array with characters/numbers to string [1, 1, 'T']  --> 2T or ['A', 1, 'T'] --> A1T
    def arr_to_str(path):
      temp = []
      add = 0
      for char in path:
        if char == 1:
          add += 1
        else:
          if add > 0:
            temp.append(str(add))
            temp.append(char)
            add = 0 
          else:
            temp.append(char)
      if add > 0:
        temp.append(str(add))
      return ''.join(temp)

    '''
    The idea to covert the original string to an array and replace each permutation of characters with 1 
    Then use arr_to_str function to append to the result
    BAT == >
      ['B', 'A', 'T']
      [1, 'A', 'T']
      [1, 1, 'T']
      [1, 1, 1]
      [1, 'A', 1]
      ['B', 1, 'T']
      ['B', 1, 1]
      ['B', 'A', 1]
    '''
    def backtrack(path, seen, index, result):
      result.append(arr_to_str(path))

      for i in range(index, len(word)):
        if i not in seen:
          seen.add(i)
          before = path[i]
          path[i] = 1
          backtrack(path, seen, i, result)
          path[i] = before
          seen.remove(i)
    
    result = []
    word_arr = list(word)
    backtrack(word_arr, set(), 0, result)
    return result