Backtracking N Queens, Subset Sum Problems is an important DAA topic because it appears in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.
For this page, focus on what problem Backtracking N Queens, Subset Sum Problems solves, where developers usually make mistakes, and how to verify the result. The audit note for this lesson was: limited checklist/practice/mistake/FAQ notes .
A strong understanding of Backtracking N Queens, Subset Sum Problems should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work with tools or output.
Backtracking N Queens Subset Sum Problems should be studied as a practical algorithm analysis lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.
In the daa > backtracking page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.
Backtracking is a general problem-solving technique used for searching all possible solutions while pruning choices that cannot lead to a valid answer. It builds a solution step by step and abandons a partial solution as soon as it becomes invalid or unpromising.
You can think of backtracking as a depth-first search on a decision tree. Each level of the tree represents a choice. When one choice fails, we undo it and try the next possibility.
This is often called the choose-explore-unchoose pattern.
Many combinational problems can be viewed as building a partial answer one step at a time. If at any point the partial answer already breaks the problem's rules, then there is no need to explore deeper. That branch can be cut immediately. This pruning is what makes backtracking more powerful than naive brute force.
| Technique | Main Idea | Key Difference |
|---|---|---|
| Brute force | Try every possibility | No pruning |
| DFS | Explore deeply before backtracking | Traversal strategy, not always constraint-based |
| Backtracking | DFS + pruning invalid branches | Stops early when a branch cannot succeed |
| Problem | Typical Choice | Constraint |
|---|---|---|
| N-Queens | Place a queen in a row | No same column or diagonal |
| Subset Sum | Include or exclude an element | Target sum must be achievable |
| Rat in a Maze | Move to a neighboring cell | Stay inside open, unvisited cells |
| Sudoku | Place a digit in a cell | Row, column, and box rules |
| Graph Coloring | Assign a color to a vertex | Adjacent vertices cannot share a color |
| Permutations / Combinations | Pick next element | Avoid duplicates or repeated use |
Most backtracking solutions follow the same recursive structure:
void backtrack(State state) {
if (isSolution(state)) {
record(state);
return;
}
for (Choice choice : choices(state)) {
if (!isValid(state, choice)) continue; // prune
apply(state, choice); // CHOOSE
backtrack(state); // EXPLORE
undo(state, choice); // UNCHOOSE
}
}The N-Queens problem asks us to place N queens on an N x N chessboard so that no two queens attack each other. Since queens attack horizontally, vertically, and diagonally, each placement must be checked carefully.
The usual backtracking idea is to place exactly one queen in each row. For every row, try every column. If a position is safe, place the queen and move to the next row. Otherwise skip that position.
public class NQueens {
static int n;
static int[] board; // board[row] = column of queen in that row
static int solutions = 0;
static boolean isSafe(int row, int col) {
for (int r = 0; r < row; r++) {
if (board[r] == col) return false; // same column
if (Math.abs(board[r] - col) == Math.abs(r - row)) return false; // diagonal
}
return true;
}
static void solve(int row) {
if (row == n) {
solutions++;
printBoard();
return;
}
for (int col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row] = col; // CHOOSE
solve(row + 1); // EXPLORE
board[row] = -1; // UNCHOOSE
}
}
}
static void printBoard() {
System.out.println("Solution " + solutions + ":");
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
System.out.print(board[r] == c ? "Q " : ". ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
n = 4;
board = new int[n];
java.util.Arrays.fill(board, -1);
solve(0);
System.out.println("Total solutions for " + n + "-Queens: " + solutions);
}
}In subset sum, we decide for each element whether to include it or exclude it. That naturally gives a binary decision tree. Backtracking becomes useful because if the current sum already exceeds the target, we may prune that branch in suitable cases.
The pruning below assumes non-negative numbers. If negative numbers are allowed, the `currentSum > target` pruning rule is not always safe.
import java.util.ArrayList;
import java.util.List;
public class SubsetSum {
// Assumes all numbers are non-negative
static void findSubsets(int[] arr, int target, int idx,
int currentSum, List<Integer> current) {
if (currentSum == target) {
System.out.println("Found: " + current);
return;
}
if (idx == arr.length || currentSum > target) return; // prune
// CHOOSE: include arr[idx]
current.add(arr[idx]);
findSubsets(arr, target, idx + 1, currentSum + arr[idx], current);
// UNCHOOSE: exclude arr[idx]
current.remove(current.size() - 1);
findSubsets(arr, target, idx + 1, currentSum, current);
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 2, 5};
int target = 6;
System.out.println("Subsets summing to " + target + ":");
findSubsets(arr, target, 0, 0, new ArrayList<>());
// Possible outputs: [3, 1, 2], [1, 5], [4, 2]
}
}In the Rat in a Maze problem, we search for paths from the source cell to the destination cell while avoiding blocked or already visited cells. At each step, the rat chooses a valid move, explores deeper, and backtracks when stuck.
public class RatInMaze {
static int N;
static int[][] maze;
static int[][] solution;
static int paths = 0;
static int[] dr = {0, 1, 0, -1};
static int[] dc = {1, 0, -1, 0};
static String[] dir = {"R", "D", "L", "U"};
static boolean isSafe(int r, int c) {
return r >= 0 && r < N && c >= 0 && c < N
&& maze[r][c] == 1 && solution[r][c] == 0;
}
static void solve(int r, int c, String path) {
if (r == N - 1 && c == N - 1) {
paths++;
System.out.println("Path " + paths + ": " + path);
return;
}
solution[r][c] = 1; // CHOOSE
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (isSafe(nr, nc)) {
solve(nr, nc, path + dir[d]); // EXPLORE
}
}
solution[r][c] = 0; // UNCHOOSE
}
public static void main(String[] args) {
N = 4;
maze = new int[][]{
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{0, 1, 1, 1}
};
solution = new int[N][N];
System.out.println("All paths from (0,0) to (" + (N-1) + "," + (N-1) + "):");
solve(0, 0, "");
System.out.println("Total paths: " + paths);
}
}Pruning means rejecting a partial solution early. Good pruning can reduce the search space dramatically.
| Problem | Pruning Rule |
|---|---|
| N-Queens | Reject positions that share a column or diagonal with an existing queen |
| Subset Sum | Stop if the current sum already exceeds the target for non-negative inputs |
| Rat in a Maze | Reject blocked cells or cells already in the current path |
| Sudoku | Reject digits that violate row, column, or subgrid constraints |
Backtracking is usually exponential in the worst case because it may have to explore many branches. However, smart pruning often makes it much faster in practice.
| Problem | Worst Case | Practical Notes |
|---|---|---|
| N-Queens | O(N!) | Pruning removes most invalid placements early |
| Subset Sum | O(2^n) | Pruning helps when the target can be exceeded quickly |
| Permutations | O(n!) | Must explore every arrangement if all outputs are required |
| Sudoku | Exponential | Constraint propagation reduces real search greatly |
| Graph Coloring | O(k^n) | Branching depends on number of colors and constraints |
| Aspect | Backtracking | Dynamic Programming |
|---|---|---|
| Main idea | Explore choices and undo bad ones | Reuse overlapping subproblem results |
| Typical goal | Search for valid solutions | Optimize value or count efficiently |
| Best for | Constraint satisfaction, enumeration, puzzles | Optimization with overlapping subproblems |
| Speed | Often exponential | Often polynomial or pseudo-polynomial after memoization/tabulation |
1. Define the input for Backtracking N Queens Subset Sum Problems.
2. Apply the rule from the lesson.
3. Compare the actual result with the expected result.
4. Record the fix if the result differs.1. Try empty, missing, duplicate, or invalid data.
2. Identify where Backtracking N Queens Subset Sum Problems changes behavior.
3. Explain the safest correction.
4. Retest the normal path.Memorizing Backtracking N Queens Subset Sum Problems without the situation where it is useful.
Connect Backtracking N Queens Subset Sum Problems to a concrete algorithm analysis task.
Testing Backtracking N Queens Subset Sum Problems only with the perfect input.
Include empty, missing, duplicate, incompatible, or failed cases when relevant.
Changing code before reading the visible symptom or error message.
Inspect the output, state, configuration, or stack trace connected to Backtracking N Queens Subset Sum Problems.
Memorizing Backtracking N Queens Subset Sum Problems without the situation where it is useful.
Connect Backtracking N Queens Subset Sum Problems to a concrete algorithm analysis task.
The common mistake is memorizing syntax without understanding when the behavior changes or fails.
Remember the problem it solves in algorithm analysis, then attach the syntax or steps to that problem.
You can predict the result of a small example, explain a failure case, and choose it over a nearby alternative for a clear reason.
They often copy the syntax but skip the state, input, dependency, selector, route, type, or configuration that controls the behavior.
Explore 500+ free tutorials across 20+ languages and frameworks.