Why Backtracking and What Greedy Cannot Solve in DSA Typescript - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start backtracking by choosing the first option.

DSA Typescript

function backtrack(options: number[], index: number): boolean {
  if (index === options.length) return true;
  // Choose option
  const choice = options[1];
  return backtrack(options, index + 1);
}

Drag options to blanks, or click blank then click option'

A[index]

B(index)

C{index}

D<index>

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses or curly braces instead of square brackets to access array elements.

We use square brackets [index] to access the element at position index in the array.

2fill in blank

medium

Complete the code to check if the current choice is valid before continuing backtracking.

DSA Typescript

function backtrack(options: number[], index: number): boolean {
  if (index === options.length) return true;
  const choice = options[index];
  if ([1]) {
    return backtrack(options, index + 1);
  }
  return false;
}

Drag options to blanks, or click blank then click option'

Achoice === index

Bchoice > 0

CisValid(choice)

Dchoice != null

Attempts:

3 left

💡 Hint

Common Mistakes

Using a simple comparison instead of a validation function.

Not checking validity before recursing.

We call a function isValid(choice) to check if the current choice can be part of the solution.

3fill in blank

hard

Fix the error in the backtracking function to correctly undo the choice after recursion.

DSA Typescript

function backtrack(options: number[], index: number, path: number[]): boolean {
  if (index === options.length) return true;
  const choice = options[index];
  if (isValid(choice)) {
    path.push(choice);
    if (backtrack(options, index + 1, path)) return true;
    [1];
  }
  return false;
}

Drag options to blanks, or click blank then click option'

Apath.splice(0, 1)

Bpath.push(choice)

Cpath.shift()

Dpath.pop()

Attempts:

3 left

💡 Hint

Common Mistakes

Using push instead of pop to undo choice.

Removing the wrong element from the path.

We remove the last choice from path using pop() to undo the choice before trying another.

4fill in blank

hard

Fill both blanks to implement a greedy approach that picks the best immediate option.

DSA Typescript

function greedySelect(options: number[]): number[] {
  const result: number[] = [];
  for (let i = 0; i < options.length; i++) {
    if (options[i] [1] 0) {
      result.[2](options[i]);
    }
  }
  return result;
}

Drag options to blanks, or click blank then click option'

A>

Bpush

C<

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push to add elements.

Using wrong comparison operator.

We pick options greater than 0 and add them to result using push().

5fill in blank

hard

Fill all three blanks to implement backtracking that tries all options and backtracks properly.

DSA Typescript

function backtrackAll(options: number[], index: number, path: number[]): boolean {
  if (index === options.length) return true;
  for (let i = 0; i < options.length; i++) {
    if (isValid(options[i])) {
      path.[1](options[i]);
      if (backtrackAll(options, index + 1, path)) return true;
      path.[2]();
    }
  }
  return false;
}

const result = backtrackAll([3], 0, []);

Drag options to blanks, or click blank then click option'

Apush

Bpop

Coptions

Dpath

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting to backtrack by popping from path.

Passing wrong variable as options.

We add choices with push(), remove them with pop(), and start with the options array.