docstr: Backtrack the cost table and retrieve the optimal checkpointing strategy.
  
  Args:
      chain (Chain): A basic linearized structure for solving the dynamic programming problem.
      lhs (int): The left index of the interval to backtrack.
      rhs (int): The right index of the interval to backtrack.
      budget (int): The memory budget for processing this interval.
      cost_table (List[Any]): See ``._compute_table()`` for definitions
      back_ptr (List[Any]): See ``._compute_table()`` for definitions
  
  Raises:
      ValueError: Can not process the chain.
  
  Returns:
      sequence (Sequence): The sequence of executing nodes with checkpoints.
docstr_tok: ["Backtrack","the","cost","table","and","retrieve","the","optimal","checkpointing","strategy",".","Args",":","chain","(","Chain",")",":","A","basic","linearized","structure","for","solving","the","dynamic","programming","problem",".","lhs","(","int",")",":","The","left","index","of","the","interval","to","backtrack",".","rhs","(","int",")",":","The","right","index","of","the","interval","to","backtrack",".","budget","(","int",")",":","The","memory","budget","for","processing","this","interval",".","cost_table","(","List","[","Any","]",")",":","See","``","._compute_table","(",")","``","for","definitions","back_ptr","(","List","[","Any","]",")",":","See","``","._compute_table","(",")","``","for","definitions","Raises",":","ValueError",":","Can","not","process","the","chain",".","Returns",":","sequence","(","Sequence",")",":","The","sequence","of","executing","nodes","with","checkpoints","."]
code: def _backtrack(
      chain: Chain,
      lhs: int,
      rhs: int,
      budget: int,
      cost_table: List[Any],
      back_ptr: List[Any],
  ) -> "Sequence":
      """Backtrack the cost table and retrieve the optimal checkpointing strategy.
  
      Args:
          chain (Chain): A basic linearized structure for solving the dynamic programming problem.
          lhs (int): The left index of the interval to backtrack.
          rhs (int): The right index of the interval to backtrack.
          budget (int): The memory budget for processing this interval.
          cost_table (List[Any]): See ``._compute_table()`` for definitions
          back_ptr (List[Any]): See ``._compute_table()`` for definitions
  
      Raises:
          ValueError: Can not process the chain.
  
      Returns:
          sequence (Sequence): The sequence of executing nodes with checkpoints.
      """
      if budget <= 0:
          raise ValueError(
              f"Can not process a chain with negative memory {budget}"
          )
      elif cost_table[budget][lhs][rhs] == float("inf"):
          raise ValueError(
              f"Can not process this chain from index {lhs} to {rhs} with memory {budget}"
          )
  
      sequence = Sequence()
      if rhs == lhs:
          if lhs == len(chain):
              sequence += [Loss()]
          else:
              sequence += [ForwardEnable(lhs), Backward(lhs)]
          return sequence
  
      if back_ptr[budget][lhs][rhs][0]:
          sequence += [
              ForwardEnable(lhs),
              CheckpointSolverRotor._backtrack(
                  chain,
                  lhs + 1,
                  rhs,
                  budget - chain.xbar[lhs + 1],
                  cost_table,
                  back_ptr,
              ),
              Backward(lhs),
          ]
      else:
          best_leaf = back_ptr[budget][lhs][rhs][1]
          sequence += [ForwardCheck(lhs)]
          sequence += [
              ForwardNograd(k) for k in range(lhs + 1, best_leaf)
          ]
          sequence += [
              CheckpointSolverRotor._backtrack(
                  chain,
                  best_leaf,
                  rhs,
                  budget - chain.x[best_leaf],
                  cost_table,
                  back_ptr,
              ),
              CheckpointSolverRotor._backtrack(
                  chain,
                  lhs,
                  best_leaf - 1,
                  budget,
                  cost_table,
                  back_ptr,
              ),
          ]
      return sequence
  
imports: from copy import deepcopy
  from typing import Any, List, Tuple
  from torch import Tensor
  from torch.fx import Graph, Node
  from colossalai.auto_parallel.passes.runtime_apply_pass import runtime_apply, runtime_comm_spec_apply
  from colossalai.fx.codegen.activation_checkpoint_codegen import _find_nested_ckpt_regions
  from colossalai.fx.profiler import activation_size, calculate_bwd_time, calculate_fwd_out, calculate_fwd_time, calculate_fwd_tmp
  from colossalai.logging import get_dist_logger
  from .ckpt_solver_base import CheckpointSolverBase
  from .operation import Backward, Chain, ForwardCheck, ForwardEnable, ForwardNograd, Loss, Sequence
label_desc: Use image node_id 12 for calling the CheckpointSolverRotor obj's underlying member method code with example usage: obj._backtrack(chain, lhs, rhs, budget, cost_table, back_ptr) and returns: sequence, sequence