← Back to DSA Course | Chapter 8: Recursion & Backtracking | Lesson 4 of 7

Backtracking परिचय

Backtracking एक maze में चलने और, जब भी आप एक dead end पर पहुंचें, आखिरी choice पर वापस कदम रखने और दूसरा path try करने जैसा है।

In this page:

  1. Backtracking Idea
  2. State and Undo
  3. Decision Tree
  4. Pruning
  5. Practice
Syntax
markup 
def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for choice in choices:
        make(choice)        # choose
        backtrack(state)    # explore
        undo(choice)        # un-choose

Backtracking Idea

Backtracking किसी problem के possible choices को systematically explore करता है, और जब भी एक choice कहीं ऐसा ले जाती है जो काम नहीं कर सकता, यह उस path को छोड़ देता है और एक dead end के नीचे जारी रखने के बजाय एक अलग चुनता है। यह essentially organized trial-and-error है एक खराब decision undo करने की क्षमता के साथ।

उदाहरण: Backtracking Idea

#include <iostream>
using namespace std;
void tryPath(int choice) {
	if (choice > 3) return;
	cout << "Trying choice " << choice << endl;
	tryPath(choice + 1);
}
int main() {
	tryPath(1);
	return 0;
}
public class Main {
	static void tryPath(int choice) {
		if (choice > 3) return;
		System.out.println("Trying choice " + choice);
		tryPath(choice + 1);
	}
	public static void main(String[] args) {
		tryPath(1);
	}
}
def try_path(choice):
    if choice > 3:
        return
    print("Trying choice", choice)
    try_path(choice + 1)

try_path(1)
#include <stdio.h>
void tryPath(int choice) {
	if (choice > 3) return;
	printf("Trying choice %d\n", choice);
	tryPath(choice + 1);
}
int main() {
	tryPath(1);
	return 0;
}

State and Undo

Code में, इसका आमतौर पर मतलब है एक choice reflect करने के लिए कुछ shared state modify करना, उस choice कहां ले जाती है explore करने के लिए recurse करना, और फिर अगले level पर अगली choice try करने से पहले उसी state change को revert करना। यह undo step वही है जो backtracking को plain recursive search से अलग बनाता है।

उदाहरण: State and Undo

#include <iostream>
#include <vector>
using namespace std;
vector<int> path;
void explore(int n) {
	if (n == 0) { for (int x : path) cout << x << " "; cout << endl; return; }
	path.push_back(n);
	explore(n - 1);
	path.pop_back();
}
int main() {
	explore(3);
	return 0;
}
import java.util.*;
public class Main {
	static List<Integer> path = new ArrayList<>();
	static void explore(int n) {
		if (n == 0) { System.out.println(path); return; }
		path.add(n);
		explore(n - 1);
		path.remove(path.size() - 1);
	}
	public static void main(String[] args) {
		explore(3);
	}
}
path = []
def explore(n):
    if n == 0:
        print(path)
        return
    path.append(n)
    explore(n - 1)
    path.pop()

explore(3)
#include <stdio.h>
int path[10], top = 0;
void explore(int n) {
	if (n == 0) { for (int i = 0; i < top; i++) printf("%d ", path[i]); printf("\n"); return; }
	path[top++] = n;
	explore(n - 1);
	top--;
}
int main() {
	explore(3);
	return 0;
}

Decision Tree

हर choice point कई possibilities में branch होता है, और उन सभी को follow करना एक decision tree बनाता है जहां root से leaf तक हर path choices का एक complete sequence represent करता है। Backtracking असल में इस tree के through एक depth-first walk है।

उदाहरण: Decision Tree

#include <iostream>
using namespace std;
void choices(string prefix, int depth) {
	if (depth == 0) { cout << prefix << endl; return; }
	choices(prefix + "0", depth - 1);
	choices(prefix + "1", depth - 1);
}
int main() {
	choices("", 3);
	return 0;
}
public class Main {
	static void choices(String prefix, int depth) {
		if (depth == 0) { System.out.println(prefix); return; }
		choices(prefix + "0", depth - 1);
		choices(prefix + "1", depth - 1);
	}
	public static void main(String[] args) {
		choices("", 3);
	}
}
def choices(prefix, depth):
    if depth == 0:
        print(prefix)
        return
    choices(prefix + "0", depth - 1)
    choices(prefix + "1", depth - 1)

choices("", 3)
#include <stdio.h>
#include <string.h>
void choices(char *prefix, int depth) {
	if (depth == 0) { printf("%s\n", prefix); return; }
	char next[10];
	sprintf(next, "%s0", prefix); choices(next, depth - 1);
	sprintf(next, "%s1", prefix); choices(next, depth - 1);
}
int main() {
	choices("", 3);
	return 0;
}

Pruning

Pruning का मतलब है जल्दी पहचानना कि एक partial choice कभी एक valid solution की ओर नहीं ले जा सकता, इसलिए आप उस branch के बाकी हिस्से को explore करना पूरी तरह skip कर देते हैं बजाय इसे पूरी तरह एक guaranteed failure तक follow करने के। अच्छी pruning अक्सर वही है जो एक अन्यथा-slow backtracking solution को इतना fast बनाती है कि चल सके।

उदाहरण: Pruning

#include <iostream>
using namespace std;
void search(int sum, int target) {
	if (sum > target) return;
	if (sum == target) { cout << "Found sum " << sum << endl; return; }
	search(sum + 2, target);
	search(sum + 3, target);
}
int main() {
	search(0, 7);
	return 0;
}
public class Main {
	static void search(int sum, int target) {
		if (sum > target) return;
		if (sum == target) { System.out.println("Found sum " + sum); return; }
		search(sum + 2, target);
		search(sum + 3, target);
	}
	public static void main(String[] args) {
		search(0, 7);
	}
}
def search(total, target):
    if total > target:
        return
    if total == target:
        print("Found sum", total)
        return
    search(total + 2, target)
    search(total + 3, target)

search(0, 7)
#include <stdio.h>
void search(int sum, int target) {
	if (sum > target) return;
	if (sum == target) { printf("Found sum %d\n", sum); return; }
	search(sum + 2, target);
	search(sum + 3, target);
}
int main() {
	search(0, 7);
	return 0;
}

Practice

Backtracking उन problems के लिए standard tool है जो आपसे सभी valid arrangements generate या count करने को कहती हैं — combinations, permutations, Sudoku और N-Queens जैसी board puzzles, और सामान्य रूप से constraint-satisfaction problems।

उदाहरण: Practice

#include <iostream>
#include <vector>
using namespace std;
void combos(vector<int>& cur, int start, int n) {
	cout << "{ "; for (int x : cur) cout << x << " "; cout << "}" << endl;
	for (int i = start; i <= n; i++) {
		cur.push_back(i);
		combos(cur, i + 1, n);
		cur.pop_back();
	}
}
int main() {
	vector<int> cur;
	combos(cur, 1, 3);
	return 0;
}
import java.util.*;
public class Main {
	static void combos(List<Integer> cur, int start, int n) {
		System.out.println(cur);
		for (int i = start; i <= n; i++) {
			cur.add(i);
			combos(cur, i + 1, n);
			cur.remove(cur.size() - 1);
		}
	}
	public static void main(String[] args) {
		combos(new ArrayList<>(), 1, 3);
	}
}
def combos(cur, start, n):
    print(cur)
    for i in range(start, n + 1):
        cur.append(i)
        combos(cur, i + 1, n)
        cur.pop()

combos([], 1, 3)
#include <stdio.h>
int cur[10], top = 0;
void combos(int start, int n) {
	printf("{ "); for (int i = 0; i < top; i++) printf("%d ", cur[i]); printf("}\n");
	for (int i = start; i <= n; i++) {
		cur[top++] = i;
		combos(i + 1, n);
		top--;
	}
}
int main() {
	combos(1, 3);
	return 0;
}
Related Topics

Tower of Hanoi समस्या · N-Queens समस्या · Fibonacci और Factorial · Sudoku Solver कैसे बनाएँ

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Recursive call के बाद choice undo करना भूल जाना (path.pop_back()), इसलिए state दूसरे branches में leak होता है।
  2. वह base case missing जो एक solution record करता है, इसलिए कभी कुछ collect नहीं होता।
  3. Invalid choices को जल्दी prune न करना, जो search को brute force में बदल देता है।
🔒

Chapter Quiz — Complete all 7 topics to unlock

0/7 topics done

Complete these topics first:

← Previous Lesson Tower of Hanoi Next Lesson → N-Queens Problem

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.