21. Backtracking

# Two types of Recursion-

1. parameterised- ans is in the parameters of the function call and it gets updated in each call

2. functional- function returns answer in each call

---------------------------------------------------------------------------------------------------------------
# Note-

1. Subsequence is formed by either picking or skipping each element while maintaining order. 

2. Subset do not follow any order in the elements
3. For n elements there are 2^n subsequences.
4. If you get duplicates, then first sort the array and then in the backtracking code, in the not take part remember to take into effect of skipping other same elements.
5. order: (base case check--> pruning --> recursion )
6.  In backtracking, any value you want to accumulate across recursive calls must be passed by reference
7. Types of pick not pick- print all/ count / check if exists / print any one

-----

# converting print all to print any one code-

- Stop and return the answer the moment you get a valid answer.
- convert function return type from "void" to "bool"

-------
8.

---------------------------------------------------------------------------------------------------------------

# 4 Recursion patterns-

1. Binary recursion- 

- at each index you make a binary choice of take or not take for the element
- avoid duplicates:

   - either, sort the vector at first and use a 2d vector to store the answer, but use a while loop       to avoid duplicates before performing not pick case
   - or, sort the vector at first and use a set to store the answer , else code is same.

2. For loop backtracking

- at each step you loop through all remaining elements and branch from each one.
- used when we have duplicate inputs & we want unique outputs

3. Permutation problems-

4. Grid based backtracking-

---------------------------------------------------------------------------------------------------------------

1. Printing all Subsequences-

(Power Set)

time: O(2^n)

Recursion tree- At each index we have 2 choices: take or not take, the current element into answer vector

-----------------------------------------------------------------------------------------------------------------------------

2. Printing all Subsequences with sum = k

same as print all subsequences, except that now
when we reach end, we print only if sum = k
so we now track sum also, during recursion

-----------------------------------------------------------------------------------------------------------------------------

3. Check if any Subsequence with sum K exists

same as old code, just that now we : return true/ false

----------------------------------------------------------------------------------------------------------------------------

4. Count no. of Subsequences

same as old code, just that now we : return count

Also, we can use a global counter and a void return type recursive function for the same

-----------------------------------------------------------------------------------------------------------------------------

5. Combination Sum-I

- Print all subsequences with sum = k

- input = distinct elements

- output = unique combinations

- an element can be used any no. of times⭐
----------------------------------------------

Approach: 
- same as take or not take
- but now, in take case, we stay at i-th index as we are allowed to take duplicates
- also, base case is different, as we add a new base case to check if we reached target sum

---------------

we can also decrease target at each choice instead of having a sum variable and in base case then we can check if target is 0 or not

-----------------------------------------------------------------------------------------------------------------------------

6. Combination Sum-II⭐

- Print all combinations with sum = k

- input = may have duplicates⭐

- output = unique combinations

- an element can be used only once

return answer in lexicographically sorted order

---------------------------------------------------------

Brute:  simple backtracking but use set for avoiding duplicates

we can also store it in 2d vector instead of a set
but then for not take case, before not take code we would have to run an additional loop to skip duplicates

----------------------------------------------------------

Optimal:  for loop backtracking

- to detect duplicates, we first sort the given array
- to skip duplicate elements in same level of recursion tree, run a for loop on current index, to pick next suitable element

-----------------------------------------------------------------------------------------------------------------------------

7. Subset sum

return all subset sums in increasing order

---------------------------------------------------------------------------------------------------------------

8. Subsets-II

Brute:   
do same as simple backtracking code for subset-I

then push all the answers into a subset to eliminate duplicates

--------------------------------

Better:   

use for loop backtracking

-----------------------------------------------------------------------------------------------------------------------------

9. Permutations-I

# Permutations-
1. order matters
2. total n! permutations
3. we can pick any unused element next
-------------------------

Method-1: time: O(n*n!)   space: O(n)

Backtracking with visited array

pick any unused element , mark it visited, recurse 

undo by marking it unvisited and not picking it in answer vector

------------------------------------------------------

Method-2:  time: O(n*n!)    space: O(1)

Swap based recursion

Fix one position at a time

----------------------------------------------------------------------------------------------------------------------------

10. Find K-th Permutation Sequence-⭐

Brute- 

generate and store all permutations using recursion
sort them
return K-th

-------------------------

Optimal-⭐

we use some maths 

given K is 1-based indexing, so to convert it to 0-based we work on K-1
recursively, at each step we find:

----------------------------------------------------------------------------------------------------------------------------

11. Palindrome partitioning-⭐

a partition is valid only if it gives palindromic substring before it
hence, aab| is not a valid partition to be explored
while aa|b is the one

-----------------------------------------------------------------------------------------------------------------------------

12. N- Queens:

redefine the problem as: place N queens in N rows, or N columns (hence, 2 approaches)
Each recursion level represents different possibilities of placing a queen in a row, or a col (based on approach)
-----------------------
Brute-  check() takes O(n)
(row based)

Use for loop based backtracking to place N queens one by one in each row 
For each position check if it is a valid position to place a queen 

Validity check:
- Only positions that are already filled earlier in recursion can attack the current cell.
- hence, for column approach, we only check left half (row, and upper and lower diagonal elements)
- for row approach, only check upper half (column, left diagonal, right diagonal)
-------------------------
Below, is row based approach

-------------------------------------------------------------
Optimal- check takes O(1)

Instead of scanning the board, we store which rows & diagonals are already occupied by using HASHING

-----------------------------------------------------------------------------------------------------------------------------

13. Sudoku solver-

- find empty cells in each row
- for each empty cell, find which digit is possible to be placed
- if in a row, no empty cell is possible to be filled, then backtrack 
-------------
Brute-

---------------------------------
Optimal-

we use hashing and use 3 arrays to store which numbers were already present in a row, column or a box,
box id = 3*(r/3) + (c/3) => maps any cell to one of the nine 3x3 boxes

-----------------------------------------------------------------------------------------------------------------------------

14. Rat in a Maze-

Find all paths in lexicographical order from top left to bottom right cell in a grid,
if 1=open & 0=blocked
-------
either use directions in lexicographical order- DLRU to get output itself in lexico order
or at the end, sort the answer vector

-----------------------------------------------------------------------------------------------------------------------------