Definition
- Backtracking extension – instead of picking one zero-in-degree task, try each one as the next choice and recurse.
- Undo after recursion – remove the placed task, restore its dependents' in-degrees, and try the next zero-in-degree task at the same level.
- Complete order – when the partial order holds all tasks, copy and record it as one valid topological order.
- Exponential cost – the count of topological orders can be factorial in the worst case (e.g., n independent tasks give n! orders).
- Practical limit – only useful for small graphs where the number of orders is manageable.
The National Bank of India wants to see all different legal sequences for running a small set of dependent audit steps, so reviewers can choose the one that best fits their staffing on a given day. All Tasks Scheduling Orders lists every sequence that respects the prerequisites.
Understanding the Concepts
What is the All Tasks Scheduling Orders problem?
Given a number of tasks and prerequisite pairs, enumerate every valid order in which all tasks can be completed. Unlike the single-order variant, this problem requires listing all possible topological orders. This is a combination of topological sort with backtracking.
package com.bank.audit;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class AllTaskOrders {
public static List<List<Integer>> findAllOrders(int taskCount, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[taskCount];
boolean[] used = new boolean[taskCount];
for (int i = 0; i < taskCount; i++) adj.add(new ArrayList<>());
for (int[] pre : prerequisites) {
adj.get(pre[0]).add(pre[1]);
inDegree[pre[1]]++;
}
List<List<Integer>> results = new ArrayList<>();
LinkedList<Integer> partial = new LinkedList<>();
backtrack(adj, inDegree, used, partial, taskCount, results);
return results;
}
private static void backtrack(List<List<Integer>> adj, int[] inDegree,
boolean[] used, LinkedList<Integer> partial, int taskCount,
List<List<Integer>> results) {
if (partial.size() == taskCount) {
results.add(new ArrayList<>(partial));
return;
}
for (int t = 0; t < taskCount; t++) {
if (!used[t] && inDegree[t] == 0) {
// Choose task t
used[t] = true;
partial.add(t);
for (int next : adj.get(t)) inDegree[next]--;
// Recurse
backtrack(adj, inDegree, used, partial, taskCount, results);
// Undo (backtrack)
used[t] = false;
partial.removeLast();
for (int next : adj.get(t)) inDegree[next]++;
}
}
}
}
Why does backtracking enumerate all orders?
At each step, every task with in-degree 0 is a valid next choice. By trying each one, recursing, and then undoing the choice, you systematically explore every possible sequence. The undo step restores the in-degree array and the used flags so the next iteration at the same level sees the original state.
package com.bank.audit;
public class BacktrackingDemo {
public static void trace() {
// Tasks: 0, 1, 2
// Prerequisites: 0->2, 1->2
// In-degrees: [0, 0, 2]
// Level 0: tasks 0 and 1 both have in-degree 0
// Branch 1: choose 0
// Level 1: task 1 has in-degree 0
// Choose 1 → reduce 2 to 0
// Level 2: task 2 has in-degree 0
// Choose 2 → order complete: [0, 1, 2]
// Undo 2
// Undo 1
// Undo 0
// Branch 2: choose 1
// Level 1: task 0 has in-degree 0
// Choose 0 → reduce 2 to 0
// Level 2: task 2 has in-degree 0
// Choose 2 → order complete: [1, 0, 2]
// Undo 2
// Undo 0
// Undo 1
// Results: [[0,1,2], [1,0,2]]
System.out.println(AllTaskOrders.findAllOrders(3,
new int[][]{{0,2},{1,2}}));
}
}
[[0, 1, 2], [1, 0, 2]]
Why is this exponential?
For n independent tasks (no prerequisites), every permutation is a valid topological order, giving n! orders. With dependencies, the count is smaller but can still grow rapidly. This makes the algorithm impractical for large graphs and only useful for small problem sizes.
// Independent tasks:
// 3 tasks, 0 prerequisites → 3! = 6 orders
// 4 tasks, 0 prerequisites → 4! = 24 orders
// 10 tasks, 0 prerequisites → 10! = 3,628,800 orders
// With dependencies:
// 3 tasks, 0→1, 1→2 → only 1 order: [0, 1, 2]
// 4 tasks, 0→2, 1→3 → 4 orders (interleaving two chains)
How does the undo step work?
After the recursion returns, you must restore the state to what it was before the choice. This means setting used[t] = false, removing the task from the partial order, and incrementing the in-degree of all dependents back to their pre-choice values.
// Choose:
used[t] = true;
partial.add(t);
for (int next : adj.get(t)) inDegree[next]--;
// Recurse:
backtrack(...);
// Undo:
used[t] = false;
partial.removeLast();
for (int next : adj.get(t)) inDegree[next]++;
What is the time and space complexity?
| Aspect | Complexity | Notes |
|---|---|---|
| Time | O(V! * V) worst case | Factorial orders, V work per order |
| Space | O(V + E) | Adjacency list + recursion stack |
| Practical limit | Small graphs only | 10-15 tasks at most |
What are edge cases?
Edge cases include zero tasks (return one empty order or no orders), fully connected chain (only one valid order), fully disconnected (n! orders), and a cycle (no valid orders).
package com.bank.audit;
public class EdgeCases {
public static void test() {
// Chain: 0->1->2 → only [0, 1, 2]
System.out.println(AllTaskOrders.findAllOrders(3,
new int[][]{{0,1},{1,2}}));
// Independent: 0, 1 → [0,1] and [1,0]
System.out.println(AllTaskOrders.findAllOrders(2, new int[][]{}));
// Cycle: 0->1, 1->0 → no valid orders
System.out.println(AllTaskOrders.findAllOrders(2,
new int[][]{{0,1},{1,0}}));
}
}
[[0, 1, 2]]
[[0, 1], [1, 0]]
[]
What are common mistakes?
The most common mistake is forgetting the undo step, which corrupts the state for sibling branches. Another mistake is modifying the in-degree array without restoring it, causing later branches to see incorrect prerequisite counts.
package com.bank.audit;
public class CommonMistakes {
// WRONG: no undo after recursion
// The used flags and in-degrees stay modified
// Sibling branches see corrupted state
// Fix: always undo used[t], partial, and in-degrees after recursion
}
How is this used in banking?
At the National Bank of India, audit reviewers want to see every legal sequence for a small set of dependent audit steps. Different reviewers have different staffing constraints, so they pick the sequence that fits best. The backtracking enumeration gives them all options.
package com.bank.audit;
import java.util.List;
public class AuditOrderPlanner {
public static void main(String[] args) {
// 0: Risk Assessment
// 1: Document Review
// 2: Field Verification
// 3: Final Report
int[][] prerequisites = {{0, 3}, {1, 3}, {2, 3}};
List<List<Integer>> orders = AllTaskOrders.findAllOrders(4, prerequisites);
String[] names = {"Risk Assessment", "Document Review",
"Field Verification", "Final Report"};
System.out.println("Total valid orders: " + orders.size());
for (List<Integer> order : orders) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < order.size(); i++) {
if (i > 0) sb.append(" -> ");
sb.append(names[order.get(i)]);
}
System.out.println(" " + sb);
}
}
}
Total valid orders: 6
Risk Assessment -> Document Review -> Field Verification -> Final Report
Risk Assessment -> Field Verification -> Document Review -> Final Report
Document Review -> Risk Assessment -> Field Verification -> Final Report
Document Review -> Field Verification -> Risk Assessment -> Final Report
Field Verification -> Risk Assessment -> Document Review -> Final Report
Field Verification -> Document Review -> Risk Assessment -> Final Report
Visual Overview
Backtracking Tree
==================
Tasks: 0, 1, 2 Prerequisites: 0→2, 1→2
In-degrees: [0, 0, 2]
root
/ \
pick 0 pick 1
/ \
pick 1 pick 0
/ \
pick 2 pick 2
| |
[0,1,2] [1,0,2]
Results: [[0,1,2], [1,0,2]]
Choose-Recurse-Undo Pattern
============================
For each task t with inDegree[t]==0 and not used:
┌─────────────────────┐
│ CHOOSE │
│ used[t] = true │
│ partial.add(t) │
│ for next: deg-- │
└──────────┬──────────┘
│
┌──────────▼──────────┐
│ RECURSE │
│ backtrack(...) │
└──────────┬──────────┘
│
┌──────────▼──────────┐
│ UNDO │
│ used[t] = false │
│ partial.removeLast │
│ for next: deg++ │
└─────────────────────┘
Key Takeaway
All Tasks Scheduling Orders combines the Topological Sort pattern with backtracking to enumerate every valid completion order instead of just one. At each step, every task with in-degree 0 is a valid next choice. You try each one, recurse, and then undo the choice to explore alternatives. When the partial order holds all tasks, you record it as a complete valid order.
The undo step is critical: after the recursion returns, you restore the used flag, remove the task from the partial order, and increment the dependents' in-degrees back to their pre-choice values. Without this restoration, sibling branches see corrupted state and produce wrong results.
At the National Bank of India, audit reviewers used this for a small set of dependent audit steps. Different reviewers had different staffing constraints, so they needed to see all legal sequences and pick the one that fit best. The backtracking enumeration gave them the complete set of options.
The exponential cost is the key limitation. For n independent tasks, the count of orders is n!, and even with dependencies the growth can be rapid. This is only practical for small graphs, typically 10-15 tasks at most. Explaining that the combinatorial explosion limits applicability is an important part of a complete answer.
Remember one sentence: branch on every zero-in-degree task at each step, recurse, undo to explore all choices, and the count of valid orders can be factorial.
---