Practical Performance Considerations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

"""
Techniques for managing deep recursion in backtracking algorithms.
 
Covers: iterative conversion, explicit stack management, and
handling language-specific stack limits.
"""
 
import sys
from typing import List, Any, Callable
from collections import deque
 
# ============================================
# TECHNIQUE 1: Converting Recursion to Iteration
# ============================================
 
def subset_sum_recursive(nums: List[int], target: int) -> List[List[int]]:
    """
    Standard recursive implementation.
    Stack depth: O(n) where n = len(nums)
    """
    result = []
    
    def backtrack(index: int, current: List[int], current_sum: int):
        if current_sum == target:
            result.append(current[:])
            return
        if index >= len(nums) or current_sum > target:
            return
        
        # Exclude
        backtrack(index + 1, current, current_sum)
        # Include
        current.append(nums[index])
        backtrack(index + 1, current, current_sum + nums[index])
        current.pop()
    
    backtrack(0, [], 0)
    return result
 
 
def subset_sum_iterative(nums: List[int], target: int) -> List[List[int]]:
    """
    Iterative implementation using explicit stack.
    Avoids recursion depth limits entirely.
    
    Each stack frame stores: (index, current, current_sum, phase)
    - phase 0: about to explore 'exclude'
    - phase 1: about to explore 'include'
    - phase 2: done with both, backtrack
    """
    result = []
    
    # Stack entries: (index, current_list, current_sum, phase)
    # Using indices instead of copying lists for efficiency
    stack = [(0, [], 0, 0)]
    
    while stack:
        index, current, current_sum, phase = stack.pop()
        
        # Check completion/pruning
        if current_sum == target:
            result.append(current[:])
            continue
        if index >= len(nums) or current_sum > target:
            continue
        
        if phase == 0:
            # First: push continuation for include phase
            stack.append((index, current, current_sum, 1))
            # Then: explore exclude branch
            stack.append((index + 1, current[:], current_sum, 0))
        
        elif phase == 1:
            # Explore include branch
            new_current = current + [nums[index]]
            stack.append((index + 1, new_current, current_sum + nums[index], 0))
    
    return result
 
 
# ============================================
# TECHNIQUE 2: Tail Recursion Optimization
# ============================================
 
def permutations_with_trampolining(elements: List[Any]) -> List[List[Any]]:
    """
    Trampolining pattern for languages without TCO.
    
    Instead of recursive calls, return a 'continuation' that the
    trampoline loop executes. This keeps stack depth at O(1).
    """
    result = []
    
    def make_generator():
        """Returns a generator that yields continuations."""
        stack = [(0, [], list(range(len(elements))))]
        
        while stack:
            depth, current, remaining = stack.pop()
            
            if not remaining:
                result.append([elements[i] for i in current])
                continue
            
            # Push all branches (in reverse for correct order)
            for i in range(len(remaining) - 1, -1, -1):
                elem = remaining[i]
                new_current = current + [elem]
                new_remaining = remaining[:i] + remaining[i+1:]
                stack.append((depth + 1, new_current, new_remaining))
    
    make_generator()
    return result
 
 
# ============================================
# TECHNIQUE 3: Checking and Increasing Stack Limit
# ============================================
 
def safe_deep_recursion(depth_needed: int):
    """
    Safely handle potentially deep recursion.
    """
    # Check current limit
    current_limit = sys.getrecursionlimit()
    print(f"Current Python recursion limit: {current_limit}")
    
    if depth_needed > current_limit - 100:  # Safety margin
        # Option 1: Increase limit (risky for very deep)
        if depth_needed < 10000:
            new_limit = depth_needed + 500
            sys.setrecursionlimit(new_limit)
            print(f"Increased limit to: {new_limit}")
        else:
            # Option 2: Switch to iterative
            print(f"Depth {depth_needed} too deep for recursion; use iterative version")
            return False
    
    return True
 
 
# ============================================
# DEMONSTRATION
# ============================================
 
def compare_recursive_vs_iterative():
    """
    Compare performance of recursive vs iterative implementations.
    """
    import time
    
    print("=" * 60)
    print("RECURSIVE VS ITERATIVE COMPARISON")
    print("=" * 60)
    
    nums = list(range(1, 21))  # [1, 2, ..., 20]
    target = 30
    
    # Recursive
    start = time.perf_counter()
    result_rec = subset_sum_recursive(nums, target)
    time_rec = time.perf_counter() - start
    
    # Iterative
    start = time.perf_counter()
    result_iter = subset_sum_iterative(nums, target)
    time_iter = time.perf_counter() - start
    
    print(f"
Subset sum: elements=[1..20], target={target}")
    print(f"  Recursive: {len(result_rec)} solutions in {time_rec:.4f}s")
    print(f"  Iterative: {len(result_iter)} solutions in {time_iter:.4f}s")
    print(f"  Solutions match: {sorted(map(tuple, result_rec)) == sorted(map(tuple, result_iter))}")
 
 
# Run demonstration
compare_recursive_vs_iterative()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

"""
Memory-efficient state representation techniques for backtracking.
 
Compares different approaches and demonstrates significant
memory and performance differences.
"""
 
import sys
from typing import List, Set
import tracemalloc
 
# ============================================
# TECHNIQUE 1: Modify-Restore Instead of Copy
# ============================================
 
def combinations_copying(elements: List, k: int) -> List[List]:
    """
    INEFFICIENT: Copies the current list at each step.
    Memory: O(k × C(n,k)) for solutions + O(k²) per path for copies
    """
    result = []
    
    def backtrack(start: int, current: List):
        if len(current) == k:
            result.append(current)  # Already a copy
            return
        for i in range(start, len(elements)):
            backtrack(i + 1, current + [elements[i]])  # COPY here
    
    backtrack(0, [])
    return result
 
 
def combinations_modify_restore(elements: List, k: int) -> List[List]:
    """
    EFFICIENT: Modifies and restores a single list.
    Memory: O(k × C(n,k)) for solutions + O(k) for current path
    """
    result = []
    current = []
    
    def backtrack(start: int):
        if len(current) == k:
            result.append(current[:])  # Copy only when recording
            return
        for i in range(start, len(elements)):
            current.append(elements[i])  # MODIFY
            backtrack(i + 1)
            current.pop()  # RESTORE
    
    backtrack(0)
    return result
 
 
# ============================================
# TECHNIQUE 2: Bitmask Representation
# ============================================
 
def subsets_list_based(n: int) -> int:
    """
    Generate subsets using list representation.
    Counts subsets by size.
    """
    size_counts = [0] * (n + 1)
    current = []
    
    def backtrack(index: int):
        if index == n:
            size_counts[len(current)] += 1
            return
        # Exclude
        backtrack(index + 1)
        # Include
        current.append(index)
        backtrack(index + 1)
        current.pop()
    
    backtrack(0)
    return size_counts
 
 
def subsets_bitmask(n: int) -> int:
    """
    Generate subsets using bitmask representation.
    Much more memory efficient: O(1) per subset instead of O(n).
    """
    size_counts = [0] * (n + 1)
    
    def backtrack(index: int, mask: int, size: int):
        if index == n:
            size_counts[size] += 1
            return
        # Exclude
        backtrack(index + 1, mask, size)
        # Include
        backtrack(index + 1, mask | (1 << index), size + 1)
    
    backtrack(0, 0, 0)
    return size_counts
 
 
# ============================================
# TECHNIQUE 3: Using Indices Instead of Elements
# ============================================
 
def permutations_with_copies(elements: List) -> int:
    """
    Generate permutations by tracking which elements are used.
    Uses set copies (inefficient).
    """
    count = [0]
    
    def backtrack(remaining: Set, current: List):
        if not remaining:
            count[0] += 1
            return
        for elem in list(remaining):  # List copy of set
            new_remaining = remaining - {elem}  # Set copy!
            backtrack(new_remaining, current + [elem])
    
    backtrack(set(range(len(elements))), [])
    return count[0]
 
 
def permutations_with_swapping(elements: List) -> int:
    """
    Generate permutations using in-place swapping.
    O(n) space total, no copies during recursion.
    """
    count = [0]
    arr = elements[:]  # Single working copy
    
    def backtrack(start: int):
        if start == len(arr):
            count[0] += 1
            return
        for i in range(start, len(arr)):
            arr[start], arr[i] = arr[i], arr[start]  # Swap
            backtrack(start + 1)
            arr[start], arr[i] = arr[i], arr[start]  # Restore
    
    backtrack(0)
    return count[0]
 
 
# ============================================
# MEMORY COMPARISON
# ============================================
 
def compare_memory_usage():
    """
    Compare memory usage of different approaches.
    """
    print("=" * 70)
    print("MEMORY EFFICIENCY COMPARISON")
    print("=" * 70)
    
    n = 15
    k = 7
    elements = list(range(n))
    
    # Test combinations
    print(f"
Combinations: C({n},{k})")
    print("-" * 40)
    
    tracemalloc.start()
    result1 = combinations_copying(elements, k)
    current1, peak1 = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    
    tracemalloc.start()
    result2 = combinations_modify_restore(elements, k)
    current2, peak2 = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    
    print(f"  Copying approach:       Peak = {peak1 / 1024:.1f} KB")
    print(f"  Modify-restore approach: Peak = {peak2 / 1024:.1f} KB")
    print(f"  Memory saved: {(1 - peak2/peak1) * 100:.1f}%")
    
    # Test subsets
    print(f"
Subset representation: n={n}")
    print("-" * 40)
    
    tracemalloc.start()
    counts1 = subsets_list_based(n)
    current, peak1 = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    
    tracemalloc.start()
    counts2 = subsets_bitmask(n)
    current, peak2 = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    
    print(f"  List-based:    Peak = {peak1 / 1024:.1f} KB")
    print(f"  Bitmask-based: Peak = {peak2 / 1024:.1f} KB")
    print(f"  Memory saved: {(1 - peak2/peak1) * 100:.1f}%")
 
 
# Run comparison
compare_memory_usage()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

"""
Profiling infrastructure for backtracking algorithms.
 
Provides detailed metrics to guide optimization efforts.
"""
 
import time
import functools
from typing import Callable, Any, Dict, List
from dataclasses import dataclass, field
from collections import defaultdict
 
@dataclass
class BacktrackingMetrics:
    """Comprehensive metrics for backtracking analysis."""
    total_nodes: int = 0
    nodes_by_depth: Dict[int, int] = field(default_factory=lambda: defaultdict(int))
    pruned_by_depth: Dict[int, int] = field(default_factory=lambda: defaultdict(int))
    solutions_found: int = 0
    max_depth_reached: int = 0
    constraint_checks: int = 0
    constraint_time_ns: int = 0
    total_time_ns: int = 0
    
    @property
    def nodes_per_solution(self) -> float:
        if self.solutions_found == 0:
            return float('inf')
        return self.total_nodes / self.solutions_found
    
    @property
    def avg_time_per_node_ns(self) -> float:
        if self.total_nodes == 0:
            return 0
        return self.total_time_ns / self.total_nodes
    
    def pruning_rate_at_depth(self, depth: int) -> float:
        visited = self.nodes_by_depth.get(depth, 0)
        pruned = self.pruned_by_depth.get(depth, 0)
        total = visited + pruned
        if total == 0:
            return 0.0
        return pruned / total
    
    def report(self) -> str:
        lines = [
            "=" * 50,
            "BACKTRACKING PROFILING REPORT",
            "=" * 50,
            f"Total nodes explored: {self.total_nodes:,}",
            f"Solutions found: {self.solutions_found:,}",
            f"Nodes per solution: {self.nodes_per_solution:.1f}",
            f"Max depth reached: {self.max_depth_reached}",
            f"Total time: {self.total_time_ns / 1e6:.2f} ms",
            f"Avg time per node: {self.avg_time_per_node_ns:.0f} ns",
            "",
            "Exploration by depth:",
        ]
        
        for d in sorted(self.nodes_by_depth.keys()):
            visited = self.nodes_by_depth[d]
            pruned = self.pruned_by_depth[d]
            rate = self.pruning_rate_at_depth(d)
            lines.append(f"  Depth {d:2d}: {visited:>8,} visited, "
                        f"{pruned:>8,} pruned ({rate*100:5.1f}%)")
        
        lines.append("=" * 50)
        return "
".join(lines)
 
 
class ProfiledBacktracker:
    """
    Wrapper that adds profiling to backtracking algorithms.
    
    Usage:
        profiler = ProfiledBacktracker()
        
        @profiler.track
        def backtrack(state, depth):
            ...
            if should_prune:
                profiler.record_prune(depth)
                return
            ...
    """
    
    def __init__(self):
        self.metrics = BacktrackingMetrics()
        self._start_time = 0
    
    def reset(self):
        self.metrics = BacktrackingMetrics()
    
    def start(self):
        self._start_time = time.perf_counter_ns()
    
    def stop(self):
        self.metrics.total_time_ns = time.perf_counter_ns() - self._start_time
    
    def visit_node(self, depth: int):
        self.metrics.total_nodes += 1
        self.metrics.nodes_by_depth[depth] += 1
        self.metrics.max_depth_reached = max(
            self.metrics.max_depth_reached, depth
        )
    
    def record_prune(self, depth: int):
        self.metrics.pruned_by_depth[depth] += 1
    
    def record_solution(self):
        self.metrics.solutions_found += 1
    
    def timed_constraint_check(self, check_func: Callable[[], bool]) -> bool:
        start = time.perf_counter_ns()
        result = check_func()
        elapsed = time.perf_counter_ns() - start
        self.metrics.constraint_checks += 1
        self.metrics.constraint_time_ns += elapsed
        return result
 
 
def demonstrate_profiling():
    """
    Demonstrate profiling on N-Queens problem.
    """
    print("=" * 60)
    print("PROFILED N-QUEENS DEMONSTRATION")
    print("=" * 60)
    
    for n in [8, 10, 12]:
        profiler = ProfiledBacktracker()
        
        def solve_nqueens():
            profiler.start()
            
            cols = set()
            diag1 = set()
            diag2 = set()
            
            def backtrack(row: int):
                profiler.visit_node(row)
                
                if row == n:
                    profiler.record_solution()
                    return
                
                for col in range(n):
                    if col in cols or (row - col) in diag1 or (row + col) in diag2:
                        profiler.record_prune(row)
                        continue
                    
                    cols.add(col)
                    diag1.add(row - col)
                    diag2.add(row + col)
                    
                    backtrack(row + 1)
                    
                    cols.remove(col)
                    diag1.remove(row - col)
                    diag2.remove(row + col)
            
            backtrack(0)
            profiler.stop()
        
        solve_nqueens()
        
        print(f"
{n}-Queens:")
        print(profiler.metrics.report())
 
 
# Run demonstration
demonstrate_profiling()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

"""
Implementing timeout handling for backtracking algorithms.
 
Shows multiple strategies for respecting time budgets.
"""
 
import time
import signal
import threading
from typing import Optional, List, Any, Callable
from dataclasses import dataclass
from contextlib import contextmanager
 
# ============================================
# STRATEGY 1: Periodic Time Checks
# ============================================
 
@dataclass
class TimeoutState:
    """Shared state for timeout checking."""
    start_time: float = 0
    timeout_seconds: float = 0
    nodes_checked: int = 0
    check_frequency: int = 1000  # Check every N nodes
    timed_out: bool = False
 
def backtrack_with_timeout_check(
    problem_func: Callable,
    timeout_seconds: float = 5.0,
    check_frequency: int = 1000
) -> tuple:
    """
    Wrap backtracking with periodic timeout checks.
    
    Returns: (result, timed_out, nodes_explored, time_elapsed)
    """
    state = TimeoutState(
        start_time=time.perf_counter(),
        timeout_seconds=timeout_seconds,
        check_frequency=check_frequency
    )
    
    def check_timeout():
        """Call this periodically within the backtracking function."""
        state.nodes_checked += 1
        if state.nodes_checked % state.check_frequency == 0:
            elapsed = time.perf_counter() - state.start_time
            if elapsed > state.timeout_seconds:
                state.timed_out = True
                return True
        return state.timed_out
    
    # Inject the check function into the problem
    result = problem_func(check_timeout)
    
    elapsed = time.perf_counter() - state.start_time
    return result, state.timed_out, state.nodes_checked, elapsed
 
 
def nqueens_with_timeout(n: int, check_timeout: Callable[[], bool]) -> List:
    """
    N-Queens with integrated timeout checking.
    """
    solutions = []
    
    def backtrack(row, cols, d1, d2):
        if check_timeout():
            return  # Abort: timeout reached
        
        if row == n:
            solutions.append(list(cols))
            return
        
        for col in range(n):
            if col in cols or (row - col) in d1 or (row + col) in d2:
                continue
            cols.add(col)
            d1.add(row - col)
            d2.add(row + col)
            backtrack(row + 1, cols, d1, d2)
            if check_timeout():
                cols.remove(col)
                return  # Propagate timeout
            cols.remove(col)
            d1.remove(row - col)
            d2.remove(row + col)
    
    backtrack(0, set(), set(), set())
    return solutions
 
 
# ============================================
# STRATEGY 2: Thread-Based Timeout
# ============================================
 
def run_with_thread_timeout(
    func: Callable[[], Any],
    timeout_seconds: float
) -> tuple:
    """
    Run function in separate thread with timeout.
    
    Returns: (result, timed_out, exception)
    Note: This doesn't actually stop the computation, just stops waiting!
    """
    result = [None]
    exception = [None]
    completed = threading.Event()
    
    def worker():
        try:
            result[0] = func()
        except Exception as e:
            exception[0] = e
        finally:
            completed.set()
    
    thread = threading.Thread(target=worker)
    thread.daemon = True  # Allow program to exit even if thread running
    thread.start()
    
    timed_out = not completed.wait(timeout=timeout_seconds)
    
    if timed_out:
        # Note: Thread continues running! This just returns early.
        return None, True, None
    
    return result[0], False, exception[0]
 
 
# ============================================
# STRATEGY 3: Interruptible Iterator Pattern
# ============================================
 
class InterruptibleBacktracker:
    """
    Backtracking as an iterator that can be interrupted.
    
    Usage:
        solver = InterruptibleBacktracker(...)
        solutions = []
        for solution in solver.generate():
            solutions.append(solution)
            if len(solutions) >= max_needed:
                break  # Clean interruption
            if time.time() > deadline:
                break  # Timeout
    """
    
    def __init__(self, elements: List[Any]):
        self.elements = elements
        self.n = len(elements)
    
    def generate_permutations(self):
        """Generator that yields permutations one at a time."""
        current = []
        used = [False] * self.n
        
        def backtrack():
            if len(current) == self.n:
                yield current[:]
                return
            
            for i in range(self.n):
                if not used[i]:
                    current.append(self.elements[i])
                    used[i] = True
                    yield from backtrack()
                    current.pop()
                    used[i] = False
        
        yield from backtrack()
 
 
# ============================================
# DEMONSTRATION
# ============================================
 
def demonstrate_timeout_strategies():
    """
    Demonstrate different timeout approaches.
    """
    print("=" * 60)
    print("TIMEOUT STRATEGIES DEMONSTRATION")
    print("=" * 60)
    
    # Strategy 1: Periodic checks
    print("
1. Periodic Time Checks (N-Queens n=14, timeout=0.5s):")
    print("-" * 50)
    
    def problem(check_timeout):
        return nqueens_with_timeout(14, check_timeout)
    
    result, timed_out, nodes, elapsed = backtrack_with_timeout_check(
        problem, timeout_seconds=0.5
    )
    
    print(f"   Timed out: {timed_out}")
    print(f"   Solutions found: {len(result)}")
    print(f"   Nodes explored: {nodes:,}")
    print(f"   Time elapsed: {elapsed:.3f}s")
    
    # Strategy 2: Iterator with external control
    print("
2. Interruptible Iterator (Permutations, first 100):")
    print("-" * 50)
    
    solver = InterruptibleBacktracker([1, 2, 3, 4, 5, 6, 7, 8])
    
    start = time.perf_counter()
    count = 0
    deadline = start + 0.1  # 100ms budget
    
    for perm in solver.generate_permutations():
        count += 1
        if count >= 100 or time.perf_counter() > deadline:
            break
    
    elapsed = time.perf_counter() - start
    print(f"   Collected: {count} permutations")
    print(f"   Time elapsed: {elapsed*1000:.1f}ms")
 
 
# Run demonstration
demonstrate_timeout_strategies()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

"""
Debugging techniques for backtracking algorithms.
"""
 
from typing import List, Any
 
def backtrack_with_tracing(elements: List[Any], target_size: int):
    """
    Backtracking with full execution trace for debugging.
    
    Shows:
    - Entry to each recursive level
    - Choices made
    - Backtracking (undoing choices)
    - Solutions found
    """
    solutions = []
    trace = []
    indent = [0]
    
    def log(message: str):
        trace.append("  " * indent[0] + message)
    
    def backtrack(current: List, remaining: List):
        log(f"ENTER: current={current}, remaining={remaining}")
        indent[0] += 1
        
        if len(current) == target_size:
            log(f"** SOLUTION FOUND: {current} **")
            solutions.append(current[:])
            indent[0] -= 1
            log(f"EXIT (solution)")
            return
        
        if not remaining:
            indent[0] -= 1
            log(f"EXIT (no more elements)")
            return
        
        for i, elem in enumerate(remaining):
            log(f"CHOOSE: {elem}")
            current.append(elem)
            new_remaining = remaining[:i] + remaining[i+1:]
            
            backtrack(current, new_remaining)
            
            current.pop()
            log(f"UNCHOOSE: {elem}")
        
        indent[0] -= 1
        log(f"EXIT (tried all choices)")
    
    backtrack([], elements)
    
    return solutions, trace
 
 
def validate_backtracking_correctness():
    """
    Validate backtracking implementation against brute force.
    """
    print("=" * 60)
    print("CORRECTNESS VALIDATION")
    print("=" * 60)
    
    from itertools import combinations
    
    # Test: Generate all 2-combinations of [1,2,3,4]
    elements = [1, 2, 3, 4]
    target_size = 2
    
    # Backtracking result
    bt_solutions, _ = backtrack_with_tracing(elements, target_size)
    bt_set = set(tuple(sorted(s)) for s in bt_solutions)
    
    # Brute force (itertools)
    bf_solutions = list(combinations(elements, target_size))
    bf_set = set(bf_solutions)
    
    print(f"
Test: {target_size}-combinations of {elements}")
    print(f"Backtracking found: {len(bt_solutions)} solutions")
    print(f"Brute force found: {len(bf_solutions)} solutions")
    print(f"Match: {bt_set == bf_set}")
    
    if bt_set != bf_set:
        print(f"Missing from backtracking: {bf_set - bt_set}")
        print(f"Extra in backtracking: {bt_set - bf_set}")
 
 
def show_trace_example():
    """
    Show execution trace for a small example.
    """
    print("
" + "=" * 60)
    print("EXECUTION TRACE EXAMPLE")
    print("=" * 60)
    
    solutions, trace = backtrack_with_tracing(['A', 'B', 'C'], 2)
    
    print("
Trace (first 30 lines):")
    for line in trace[:30]:
        print(line)
    if len(trace) > 30:
        print(f"  ... ({len(trace) - 30} more lines)")
    
    print(f"
Solutions found: {solutions}")
 
 
# Run debugging demonstrations
validate_backtracking_correctness()
show_trace_example()