# Backtracking
\
## Backtracking Concept
* Select one option when multiple choices exist
* When a choice is made, a new set of choices is generated
* Continue making choices until reaching a final state
* If you keep making correct choices, you reach the goal state!
\
## Difference between Backtracking and DFS
* Reduce the number of attempts by not following a path if it seems unlikely to lead to a solution
* `Prunning`
* While DFS tracks all paths, Backtracking cuts off unnecessary paths early
* When there are too many cases for DFS
* DFS on problems with N! cases becomes unprocessable
* Applying Back Tracking algorithm generally reduces the number of cases, but in worst case scenarios, it still requires exponential time, making it unprocessable
* The path from root node to leaf node becomes a candidate solution, and we can find the answer among these candidates using DFS
* However, this method is inefficient because it searches all descendant nodes of nodes that have no possibility of being solutions
\
## Backtracking Technique
* After checking the promisingess of a node, if it's determined to be unpromising, backtrack to the parent node and move to the next child node
* When visiting a node:
* If the path including that node cannot be a solution, the node is unpromising
* If there's a possibility for a solution, it's promising
### Prunning
: No longer consider paths that include unpromising nodes
\
### Backtracking Algorithm Procedure
1. Perform DFS (Depth-First Search) on the state space tree
2. Check if each node is promising
3. If the node is unpromising, return to its parent node and continue searching
### N-Queen Problem
> SWEA 2806
```python
def backtrack(idx): #idx = row
global N, cnt
# Check if it's the final state, if so, it's a solution
if idx == N:
# Found it all - solution!
cnt +=1
return
# Generate candidates to choose from in this state
# Check if Node is promising : check column / upward diagonal / downward diagonal
for i in range(N):
# if column is promising and diagonals are promising
if not col[i] and not dia_1[idx +i] and not dia_2[N+i-idx-1]:
# Execute next state for all candidates
col[i] = 1
dia_1[idx+i] = 1
dia_2[N+i-idx-1] = 1
# Increase row
backtrack(idx+1)
# Remove what was used
col[i] = 0
dia_1[idx+i] = 0
dia_2[N+i-idx-1] = 0
T = int(input())
for t in range(1, T+1):
N = int(input())
# Only 1 Queen can be placed in each row
col = [0] * N # List to check column usage
# Lists to check diagonal promising
# Upward diagonal: sum of i and j is the same
dia_1 = [0] * (2*N -1) # Number diagonals by (r+c)
# Downward diagonal: difference between i-j is constant
dia_2 = [0] * (2*N -1) # Number diagonals by (N + c -r -1)
cnt = 0
backtrack(0)
print('#{} {}'.format(t,cnt))
```
### Subset
> Finding subsets
ex)
```python
# Print all subsets of {1,2,3,4,5,6,7,8,9,10} powerset where sum of elements is 10.
def backtrack(arr, idx, N, selected, sum_num):
if sum_num > 10:
return
if idx == N:
# Print if total sum is 10
if sum_num == 10:
for i in range(N):
if selected[i]:
print(arr[i], end=' ')
print()
return
#When current index is selected
selected[idx] =1
backtrack(arr, idx+1, N, selected, sum_num + arr[idx])
#When current index is not selected
selected[idx] = 0
backtrack(arr, idx+1, N, selected, sum_num )
arr = [1,2,3,4,5,6,7,8,9,10]
backtrack(arr, 0, 10, [0]*10, 0)
```
\
## Solving Problems by Building Space State Tree
### Finding Permutations using Backtracking
> The approach is similar to finding subsets
ex)
```python
def backtrack(result, selected, idx, N):
if idx == N:
print(result)
return
# Proceed to next step for available choice candidates
for i in range(N):
if not selected[i]:
selected[i] = 1
result[idx] = i
backtrack(result, selected, idx+1, N)
selected[i] = 0
N = 5
backtrack([0]*N, [0]*N, 0, N)
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://chloe-codes1.gitbook.io/til/algorithm/algorithm-basics/04_backtracking.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.