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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a subset sum equals target using backtracking.

DSA C#

bool SubsetSum(int[] nums, int target, int index) {
    if (target == 0) return true;
    if (index == nums.Length || target < 0) return false;
    return SubsetSum(nums, target - nums[index], index + 1) || SubsetSum(nums, target, [1]);
}

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

Aindex - 1

Bindex + 1

C0

Dnums.Length

Attempts:

3 left

💡 Hint

Common Mistakes

Using index - 1 causes going backward which is incorrect.

Using 0 resets the index causing infinite recursion.

We move to the next index without including the current number by increasing index by 1.

2fill in blank

medium

Complete the code to choose the next candidate in backtracking for the N-Queens problem.

DSA C#

bool IsSafe(int row, int col, int[] queens) {
    for (int i = 0; i < row; i++) {
        if (queens[i] == col || Math.Abs(queens[i] - col) == row - i) return false;
    }
    return true;
}

bool SolveNQueens(int row, int n, int[] queens) {
    if (row == n) return true;
    for (int col = 0; col < n; col++) {
        if (IsSafe(row, col, queens)) {
            queens[row] = col;
            if (SolveNQueens(row + 1, n, queens)) return true;
            queens[row] = [1];
        }
    }
    return false;
}

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

A-1

B0

Crow

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Setting to 0 may incorrectly indicate a queen placed in column 0.

Setting to row or n is invalid as they are valid indices or out of range.

Resetting queens[row] to -1 indicates no queen placed in that row after backtracking.

3fill in blank

hard

Fix the error in the greedy approach that tries to solve the subset sum problem.

DSA C#

bool GreedySubsetSum(int[] nums, int target) {
    Array.Sort(nums);
    int sum = 0;
    for (int i = nums.Length - 1; i >= 0; i--) {
        if (sum + nums[i] <= target) {
            sum += nums[i];
        }
    }
    return sum == [1];
}

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

A0

Bsum

Cnums.Length

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing sum to 0 always returns false unless target is 0.

Comparing sum to nums.Length is meaningless here.

We check if the sum equals the target to confirm subset sum success.

4fill in blank

hard

Fill both blanks to create a backtracking function that generates all subsets of a list.

DSA C#

void GenerateSubsets(int[] nums, int index, List<int> current, List<List<int>> result) {
    if (index == nums.Length) {
        result.Add(new List<int>(current));
        return;
    }
    GenerateSubsets(nums, [1], current, result);
    current.Add(nums[index]);
    GenerateSubsets(nums, [2], current, result);
    current.RemoveAt(current.Count - 1);
}

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

Aindex + 1

Bindex - 1

C0

Dnums.Length

Attempts:

3 left

💡 Hint

Common Mistakes

Using index - 1 causes infinite loops or errors.

Using 0 or nums.Length resets or skips incorrectly.

We move to the next index in both recursive calls, once without including and once including the current element.

5fill in blank

hard

Fill all three blanks to implement a greedy algorithm for activity selection problem.

DSA C#

List<int> SelectActivities(int[] start, int[] finish) {
    List<int> selected = new List<int>();
    int lastFinish = [1];
    for (int i = 0; i < start.Length; i++) {
        if (start[i] >= lastFinish) {
            selected.Add(i);
            lastFinish = [2];
        }
    }
    return selected;
}

// Assume activities are sorted by finish time
// Initialize lastFinish to [3]

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

A0

Bfinish[i]

C-1

Dstart[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing lastFinish to 0 may skip activities starting at 0.

Updating lastFinish incorrectly causes wrong selections.

Initialize lastFinish to -1 to allow first activity selection; update lastFinish to finish[i] after selecting an activity.

Practice

1. Why do we need backtracking algorithms instead of just using greedy algorithms for some problems?

easy

A. Because greedy algorithms make local optimal choices that may not lead to a global optimum.

B. Because backtracking algorithms always run faster than greedy algorithms.

C. Because greedy algorithms require more memory than backtracking.

D. Because backtracking algorithms never use recursion.

Solution

1. Step 1: Understand why backtracking is needed over greedy algorithms

   Greedy algorithms pick the best choice at each step without reconsidering previous choices. Backtracking tries all possibilities by undoing choices, ensuring global optimum is found when greedy fails.

2. Final Answer:

   Because greedy algorithms make local optimal choices that may not lead to a global optimum. -> Option A

3. Quick Check:

   Greedy local vs backtracking global = A [OK]

Hint: Greedy picks fast local best; backtracking explores all options [OK]

Common Mistakes:

• Thinking greedy is always faster and better
• Confusing recursion use in backtracking
• Assuming greedy always finds global optimum

2. Which of the following is the correct syntax to start a backtracking function in C#?

easy

A. void Backtrack(int step) { /* code */ }

B. int Backtrack[] { /* code */ }

C. Backtrack() => { /* code */ }

D. function Backtrack(int step) { /* code */ }

Solution

1. Step 1: Identify correct C# backtracking method syntax

   C# methods use return type, name, and parameters inside parentheses. void Backtrack(int step) { /* code */ } uses correct C# method declaration with void return and parameter.

2. Final Answer:

   void Backtrack(int step) { /* code */ } -> Option A

3. Quick Check:

   C# method syntax = C [OK]

Hint: C# methods need return type and parentheses [OK]

Common Mistakes:

• Using JavaScript or other language syntax
• Missing parentheses for parameters
• Using array brackets incorrectly

3. Consider this C# backtracking code snippet to find subsets of {1, 2}:

void Backtrack(List<int> subset, int start) {
  Console.WriteLine(string.Join(",", subset));
  for (int i = start; i < 2; i++) {
    subset.Add(i + 1);
    Backtrack(subset, i + 1);
    subset.RemoveAt(subset.Count - 1);
  }
}
Backtrack(new List<int>(), 0);

What is the printed output?

medium

A. "",1,1,2

B. "",1,2,1,2

C. ",1,2,1,2"

D. "",1,1,2,2

Solution

1. Step 1: Trace initial call, recursion, and backtracking prints

   First call prints empty subset "". Then loop adds 1, prints "1", recurses adding 2 prints "1,2". Backtracks, then adds 2 alone, prints "2". The print sequence is "",1,2,1,2.

2. Final Answer:

   "",1,2,1,2 -> Option B

3. Quick Check:

   Print sequence "",1,2,1,2 = C [OK]

Hint: Trace recursion and backtrack steps carefully [OK]

Common Mistakes:

• Confusing order of prints
• Missing empty subset print
• Not removing last element after recursion

4. The following C# code tries to solve the subset sum problem using greedy approach:

int[] nums = {3, 1, 7, 5};
int target = 8;
int sum = 0;
foreach (int num in nums) {
  if (sum + num <= target) {
    sum += num;
  }
}
Console.WriteLine(sum);

What is the problem with this code?

medium

A. It always finds the correct subset sum.

B. It causes a runtime error due to wrong loop syntax.

C. It may not find a subset that sums exactly to the target.

D. It uses backtracking instead of greedy.

Solution

1. Step 1: Analyze greedy subset sum limitation

   The code adds numbers if sum stays below target, without trying all subsets. Greedy may skip combinations that sum exactly to target, so it may fail to find exact subset.

2. Final Answer:

   It may not find a subset that sums exactly to the target. -> Option C

3. Quick Check:

   Greedy misses exact subset sums = A [OK]

Hint: Greedy skips options; subset sum needs backtracking [OK]

Common Mistakes:

• Assuming greedy always works for subset sum
• Thinking code has syntax errors
• Confusing greedy with backtracking

5. You want to find all ways to place 3 queens on a 3x3 chessboard so that no two queens attack each other. Why is backtracking necessary and greedy insufficient for this problem?

hard

A. Because greedy always finds all solutions faster than backtracking.

B. Because greedy can only solve problems with numeric inputs.

C. Because backtracking uses less memory than greedy in this problem.

D. Because greedy places queens without checking future conflicts, missing valid solutions.

Solution

1. Step 1: Understand greedy limits and backtracking advantage for N-Queens

   Greedy places queens step-by-step without revisiting choices, may cause conflicts later. Backtracking tries placing queens, and if conflict arises, removes and tries alternatives, ensuring all valid solutions.

2. Final Answer:

   Because greedy places queens without checking future conflicts, missing valid solutions. -> Option D

3. Quick Check:

   Backtracking explores all; greedy misses conflicts = B [OK]

Hint: Backtracking tries all; greedy stops early [OK]

Common Mistakes:

• Thinking greedy finds all solutions
• Confusing memory use between methods
• Assuming greedy only works with numbers