Recursion¶

/*Your task is to implement the function atoi. The function takes a string (str) as an argument and converts it to an integer and returns it.

Note: You are not allowed to use inbuilt functions.

Example 1:
Input:
str = "123"
Output: 123

Example 2:
Input:
str = "21a"
Output: -1
Explanation: Output is -1 as not all characters are digits.

Approach:
1. We start from the last character of the string and recursively convert each digit to an integer.
2. We use a helper function `getnum` that takes the index `i` and the string `str` as arguments.
3. The base case is when `i` becomes negative, in which case we return 0.
4. For each digit, we convert it to an integer by subtracting the ASCII value of '0'.
5. We check if the digit is within the range of 0 to 9. If it is, we recursively call `getnum` for the previous index `i-1`.
   - If the recursive call returns a valid number (`prev != 1e9`), we multiply it by 10 and add the current digit.
   - Otherwise, we return a large value `1e9` to indicate an invalid conversion.
6. In the main `atoi` function, we initialize `i` to the index of the last character in the string (`str.size()-1`).
7. We call the `getnum` function with `i` and `str`.
8. If the result (`ans`) is equal to `1e9`, it means the conversion was invalid, so we return -1.
9. If the first character of the string is '-', we return the negative value of `ans`.
10. Otherwise, we return `ans`.

Time Complexity: O(N), where N is the length of the string.
Space Complexity: O(N), where N is the length of the string (due to the recursive calls).

CODE:*/
int getnum(int i, string& str)
{
    if (i < 0)
        return 0;

    if (i == 0) {
        if (str[i] == '-')
            return 0;

        int digit = str[i] - '0';
        if (0 <= digit && digit <= 9) {
            int prev = getnum(i - 1, str);
            if (prev != 1e9)
                return (prev * 10) + digit;
        }
        return 1e9;
    }

    int digit = str[i] - '0';
    if (0 <= digit && digit <= 9) {
        int prev = getnum(i - 1, str);
        if (prev != 1e9)
            return (prev * 10) + digit;
    }
    return 1e9;
}

int atoi(string str)
{
    int i = str.size() - 1;
    int ans = getnum(i, str);
    if (ans == 1e9)
        return -1;
    if (str[0] == '-')
        return -1 * ans;
    return ans;
}

/*QUESTION:
A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).
Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 109 + 7.
A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:
Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:
Input: n = 4
Output: 400

Example 3:
Input: n = 50
Output: 564908303

Approach:
- We can observe that for a good digit string of length n, each digit can be either even or a prime number (2, 3, 5, or 7).
- For odd indices, there are 4 choices (2, 3, 5, or 7) since they must be prime.
- For even indices, there are 5 choices (0, 2, 4, 6, or 8) since they must be even.
- We can use a recursive approach to count the number of good digit strings.
- The base case is when n = 1, in which case there are 5 possible digit strings (0, 2, 4, 6, or 8).
- For even lengths (n % 2 == 0), we multiply the count of good digit strings of length n-1 by 4 (since there are 4 choices for odd indices).
- For odd lengths (n % 2 != 0), we multiply the count of good digit strings of length n-1 by 5 (since there are 5 choices for even indices).
- We return the result modulo 10^9 + 7 to handle large outputs.

Time Complexity: O(n) (due to the recursive calls)
Space Complexity: O(n) (due to the recursive calls)

CODE:*/

const long long mod = 1e9 + 7;

int countGoodNumbers(long long n) {
    // Base case
    if (n == 1)
        return 5;

    if (n % 2 == 0)
        return (countGoodNumbers(n - 1) % mod * 4 % mod);
    else
        return (countGoodNumbers(n - 1) % mod * 5 % mod);
}

/*QUESTION:
Reverse a given stack of 'N' integers using recursion.
Note: You are not allowed to use any extra space other than the internal stack space used due to recursion.

Example:
Input: [1,2,3,4,5]
Output: [5,4,3,2,1]

Approach:
To reverse a stack using recursion without using any extra space, we can follow the following steps:
1. Create a helper function called 'insertAtBottom' that takes an element and a stack as parameters.
2. The 'insertAtBottom' function inserts the given element at the bottom of the stack using recursion.
   - If the stack is empty, push the element to the stack and return.
   - Otherwise, pop the top element from the stack and recursively call 'insertAtBottom' with the element and the modified stack.
     After the recursive call, push the popped element back to the stack.
3. Create the main function called 'reverseStack' that reverses the given stack using recursion.
   - Base case: If the stack is empty, return.
   - Otherwise, pop the top element from the stack and recursively call 'reverseStack' on the modified stack.
     After the recursive call, call the 'insertAtBottom' function with the popped element and the modified stack.
4. The 'reverseStack' function will reverse the stack in place using recursion and the 'insertAtBottom' function.

Time Complexity: O(N^2) (due to multiple recursive calls)
Space Complexity: O(N) (due to the internal stack space used for recursion)

CODE:*/
void insertAtBottom(int ele, stack<int>& stack) {
    if (stack.empty()) {
        stack.push(ele);
        return;
    }

    int temp = stack.top();
    stack.pop();
    insertAtBottom(ele, stack);
    stack.push(temp);
}

void reverseStack(stack<int>& stack) {
    if (stack.empty())
        return;

    int first = stack.top();
    stack.pop();
    reverseStack(stack);
    insertAtBottom(first, stack);
}

/*QUESTION:
Given a stack, the task is to sort it such that the top of the stack has the greatest element.

Example 1:
Input:
Stack: 3 2 1
Output: 3 2 1

Example 2:
Input:
Stack: 11 2 32 3 41
Output: 41 32 11 3 2

Approach:
To sort a stack in descending order, we can follow the following steps:
1. Create a helper function called 'placeAtCorrectPos' that takes an element and a stack as parameters.
2. The 'placeAtCorrectPos' function places the given element at the correct position in the stack using recursion.
   - If the stack is empty or the top element of the stack is less than the given element, push the element to the stack and return.
   - Otherwise, pop the top element from the stack and recursively call 'placeAtCorrectPos' with the element and the modified stack.
     After the recursive call, push the popped element back to the stack.
3. Create the main function called 'sortSt' that sorts the stack in descending order using recursion.
   - Base case: If the stack is empty, return.
   - Otherwise, pop the top element from the stack and recursively call 'sortSt' on the modified stack.
     After the recursive call, call the 'placeAtCorrectPos' function with the popped element and the modified stack.
4. The 'sortSt' function will sort the stack in descending order using recursion and the 'placeAtCorrectPos' function.

Time Complexity: O(N^2) (due to multiple recursive calls)
Space Complexity: O(N) (due to the internal stack space used for recursion)

CODE:*/
void placeAtCorrectPos(int ele, stack<int>& st) {
    if (st.empty() || st.top() < ele) {
        st.push(ele);
        return;
    }

    int first = st.top();
    st.pop();
    placeAtCorrectPos(ele, st);
    st.push(first);
}

void sortSt(stack<int>& st) {
    if (st.empty())
        return;

    int first = st.top();
    st.pop();
    sortSt(st);
    placeAtCorrectPos(first, st);
}

/*QUESTION:
Given an integer array nums of unique elements, return all possible subsets (the power set).

Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:
Input: nums = [0]
Output: [[],[0]]

Approach:
To generate all possible subsets, we can use a recursive backtracking approach.
1. Create a helper function called 'solve' that takes a vector of vectors to store the subsets, a vector to store the current subset, the input array 'nums', and the current index as parameters.
2. In the 'solve' function:
   - If the current index is equal to the size of the input array 'nums', add the current subset to the vector of vectors.
   - Otherwise, do the following:
     - Include the element at the current index in the current subset by pushing it into the vector.
     - Recursively call the 'solve' function with the updated current subset and increment the current index.
     - Exclude the element at the current index from the current subset by popping it from the vector.
     - Recursively call the 'solve' function with the updated current subset and increment the current index.
3. Create the main function called 'subsets' that generates all possible subsets using the 'solve' function.
   - Create an empty vector of vectors to store the subsets.
   - Create an empty vector to store the current subset.
   - Call the 'solve' function with the empty vector of vectors, empty current subset, input array 'nums', and index 0.
   - Return the vector of vectors containing all the subsets.

Time Complexity: O(2^N), where N is the size of the input array 'nums'.
Space Complexity: O(N), where N is the size of the input array 'nums' (for the recursion stack and storing subsets).

CODE:*/
void solve(vector<vector<int>>& ans, vector<int>& temp, vector<int>& nums, int index) {
    if (index == nums.size()) {
        ans.push_back(temp);
        return;
    }

    // Include the element at the current index
    temp.push_back(nums[index]);
    solve(ans, temp, nums, index + 1);

    // Exclude the element at the current index
    temp.pop_back();
    solve(ans, temp, nums, index + 1);
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> temp;
    solve(ans, temp, nums, 0);
    return ans;
}

/*QUESTION:
Given a list arr of N integers, print the sums of all subsets in it.

Example:
Input:
N = 2
arr[] = {2, 3}
Output:
0 2 3 5
Explanation:
When no element is taken, the sum is 0.
When only 2 is taken, the sum is 2.
When only 3 is taken, the sum is 3.
When elements 2 and 3 are taken, the sum is 2 + 3 = 5.

Approach:
To print the sums of all subsets, we can use a recursive approach with backtracking.
1. Create a helper function called 'solve' that takes the current index, the current sum, the array, and a vector to store the sums as parameters.
2. In the 'solve' function:
   - If the current index is equal to the size of the array, add the current sum to the vector of sums and return.
   - Otherwise, do the following:
     - Include the element at the current index in the sum by recursively calling the 'solve' function with the updated index and the current sum plus the element value.
     - Exclude the element at the current index from the sum by recursively calling the 'solve' function with the updated index and the current sum.
3. Create the main function called 'subsetSums' that calculates and returns the vector of subset sums.
   - Initialize an empty vector to store the subset sums.
   - Call the 'solve' function with the initial index as 0, the initial sum as 0, the array, and the vector of subset sums.
   - Sort the vector of subset sums in ascending order.
   - Return the vector of subset sums.

Time Complexity: O(2^N), where N is the size of the array.
Space Complexity: O(N), where N is the size of the array (for recursion stack and storing subset sums).

CODE:*/
void solve(int index, int sum, vector<int>& arr, vector<int>& ans) {
    if (index == arr.size()) {
        ans.push_back(sum);
        return;
    }

    solve(index + 1, sum + arr[index], arr, ans);
    solve(index + 1, sum, arr, ans);
}

vector<int> subsetSums(vector<int> arr, int N) {
    vector<int> ans;
    int sum = 0;
    solve(0, sum, arr, ans);
    sort(ans.begin(), ans.end());
    return ans;
}

/*QUESTION:
Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Example:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example:
Input: nums = [0]
Output: [[],[0]]

Approach:
To find all possible subsets without duplicates, we can use a recursive backtracking approach.
1. Sort the input array nums in non-decreasing order to handle duplicates.
2. Create a helper function called 'solve' that takes the current index, the array nums, a temporary vector to store the current subset, and a vector of vector to store all subsets as parameters.
3. In the 'solve' function:
   - Add the current subset to the vector of subsets.
   - Iterate from the current index to the end of the array:
     - If the current index is greater than the starting index and the current element is the same as the previous element, skip the iteration to avoid duplicates.
     - Add the current element to the current subset.
     - Recursively call the 'solve' function with the updated index, the array nums, the current subset, and the vector of subsets.
     - Remove the last added element from the current subset (backtracking).
4. Create the main function called 'subsetsWithDup' that calculates and returns the vector of subsets without duplicates.
   - Sort the input array nums.
   - Initialize an empty vector to store the subsets.
   - Call the 'solve' function with the initial index as 0, the array nums, an empty temporary vector, and the vector of subsets.
   - Return the vector of subsets.

Time Complexity: O(2^N), where N is the size of the input array nums. This is because there are 2^N possible subsets.
Space Complexity: O(N), where N is the size of the input array nums. This is the space required to store the subsets.

CODE:*/

void solve(int index, vector<int>& nums, vector<int>& temp, vector<vector<int>>& ans){
    if(index==nums.size()){
        ans.push_back(temp);
        return;
    }
    // to include
    temp.push_back(nums[index]);
    solve(index+1,nums,temp,ans);
    temp.pop_back();

    // to remove duplicates
    while(index+1<nums.size() && nums[index]==nums[index+1])
        index++;

    // to exclude
    solve(index+1,nums,temp,ans);
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    vector<int> temp;
    solve(0, nums, temp, ans);
    return ans;
}

/*QUESTION:
Given an array arr[] of non-negative integers and an integer sum, the task is to count all subsets of the given array with a sum equal to the given sum. The answer can be very large, so the output will be the answer modulo 10^9 + 7.

Example:
Input: N = 6, arr[] = {2, 3, 5, 6, 8, 10}, sum = 10
Output: 3
Explanation: The subsets with a sum equal to 10 are {2, 3, 5}, {2, 8}, and {10}.

Approach:
To count the subsets with a given sum, we can use a recursive approach with backtracking.
1. Create a helper function called 'solve' that takes the current index, the remaining sum, and the array as parameters.
2. In the 'solve' function:
   - If the remaining sum is 0, return 1 (found a subset with the given sum).
   - If the index becomes 0 and the remaining sum is not 0, return 0 (no subset found with the given sum).
   - Otherwise, do the following:
     - Count the subsets that include the element at the current index by recursively calling the 'solve' function with the updated index and the remaining sum minus the element value.
     - Count the subsets that exclude the element at the current index by recursively calling the 'solve' function with the updated index and the remaining sum.
     - Return the sum of the counts from the include and exclude steps.
3. Create the main function called 'perfectSum' that calculates the count of subsets with the given sum.
   - Call the 'solve' function with the last index of the array, the given sum, and the array.
   - Return the count modulo 10^9 + 7.

Time Complexity: O(N * sum), where N is the size of the array and sum is the given sum.
Space Complexity: O(N * sum), where N is the size of the array and sum is the given sum (for recursion stack).

CODE:*/
int solve(int index, int sum, int arr[]) {
    if (sum == 0) {
        return 1;
    }
    if (index == 0) {
        return (arr[0] == sum) ? 1 : 0;
    }

    int include = 0;
    if (arr[index] <= sum)
        include = solve(index - 1, sum - arr[index], arr); // include

    int exclude = solve(index - 1, sum, arr); // exclude

    return (include + exclude) % (int)(1e9 + 7);
}

int perfectSum(int arr[], int n, int sum) {
    int cnt = solve(n - 1, sum, arr);
    return cnt % (int)(1e9 + 7);
}

/*QUESTION:
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.

Approach:
To find all unique combinations that sum up to the target, we can use a recursive backtracking approach.
1. Create a helper function called 'solve' that takes the current index, the array of candidates, the target sum, a temporary vector to store the current combination, and a vector of vector to store all combinations as parameters.
2. In the 'solve' function:
   - If the target sum is equal to 0, add the current combination to the vector of combinations.
   - If the current index is equal to the size of the array, return.
   - If the current candidate value is less than or equal to the target sum:
     - Add the current candidate to the current combination.
     - Recursively call the 'solve' function with the updated index, the same array of candidates, the reduced target sum by subtracting the current candidate value, the current combination, and the vector of combinations.
     - Remove the last added candidate from the current combination (backtracking).
   - Recursively call the 'solve' function with the updated index by incrementing it, the same array of candidates, the same target sum, the current combination, and the vector of combinations.
3. Create the main function called 'combinationSum' that calculates and returns the vector of combinations.
   - Initialize an empty vector to store the combinations.
   - Sort the array of candidates in non-decreasing order to handle duplicates.
   - Call the 'solve' function with the initial index as 0, the array of candidates, the target sum, an empty temporary vector, and the vector of combinations.
   - Return the vector of combinations.

Time Complexity: O(N^target), where N is the size of the array of candidates and target is the target sum. In the worst case, we may have to explore all possible combinations, which is exponential.
Space Complexity: O(target), as the maximum depth of the recursion tree is determined by the target sum.

CODE:*/
void solve(int index, vector<int>& candidates, int target, vector<int>& temp, vector<vector<int>>& ans) {
    if (target == 0) {
        ans.push_back(temp);
        return;
    }

    if (index == candidates.size() || target < 0)
        return;

    if (candidates[index] <= target) {
        temp.push_back(candidates[index]);
        solve(index, candidates, target - candidates[index], temp, ans);
        temp.pop_back();
    }

    solve(index + 1, candidates, target, temp, ans);
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    sort(candidates.begin(), candidates.end());
    vector<int> temp;
    solve(0, candidates, target, temp, ans);
    return ans;
}

/*QUESTION:
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. Note: The solution set must not contain duplicate combinations.

Example:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: The sum of the combinations [1,1,6], [1,2,5], [1,7], and [2,6] is equal to the target 8.

Approach:
To find all unique combinations that sum up to the target, we can use a recursive backtracking approach.
1. Create a helper function called 'solve' that takes the current index, the target sum, the array of candidates, a temporary vector to store the current combination, and a vector of vector to store all combinations as parameters.
2. Sort the array of candidates in non-decreasing order to handle duplicates.
3. In the 'solve' function:
   - If the target sum is equal to 0, add the current combination to the vector of combinations.
   - If the current index is equal to the size of the array, return.
   - If the current candidate value is less than or equal to the target sum:
     - Add the current candidate to the current combination.
     - Recursively call the 'solve' function with the updated index by incrementing it, the reduced target sum by subtracting the current candidate value, the same array of candidates, the current combination, and the vector of combinations.
     - Remove the last added candidate from the current combination (backtracking).
   - To handle duplicates, skip the candidates with the same value as the current candidate by incrementing the index until a different candidate is found.
   - Recursively call the 'solve' function with the updated index by incrementing it, the same target sum, the same array of candidates, the current combination, and the vector of combinations.
4. Create the main function called 'combinationSum2' that calculates and returns the vector of combinations.
   - Initialize an empty vector to store the combinations.
   - Call the 'solve' function with the initial index as 0, the target sum, the sorted array of candidates, an empty temporary vector, and the vector of combinations.
   - Return the vector of combinations.

Time Complexity: O(N * 2^N), where N is the size of the array of candidates. In the worst case, we may have to explore all possible combinations, which is exponential.
Space Complexity: O(target), as the maximum depth of the recursion tree is determined by the target sum.

CODE:*/
void solve(int index, int target, vector<int>& candidates, vector<int>& temp, vector<vector<int>>& ans) {
    if (target == 0) {
        ans.push_back(temp);
        return;
    }

    if (index == candidates.size() || target < 0)
        return;

    if (candidates[index] <= target) {
        temp.push_back(candidates[index]);
        solve(index + 1, target - candidates[index], candidates, temp, ans);
        temp.pop_back();
    }

    while (index + 1 < candidates.size() && candidates[index] == candidates[index + 1])
        index++;

    solve(index + 1, target, candidates, temp, ans);
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    vector<int> temp;
    sort(candidates.begin(), candidates.end());
    solve(0, target, candidates, temp, ans);
    return ans;
}

/*QUESTION:
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers 1 through 9 are used.
- Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation: 1 + 2 + 4 = 7. There are no other valid combinations.

Approach:
To find all valid combinations of k numbers that sum up to n, we can use a recursive backtracking approach.
1. Create a helper function called 'solve' that takes the current index, the number of elements to choose (k), the target sum (tar), the array of available numbers (nums), a temporary vector to store the current combination, and a vector of vector to store all combinations as parameters.
2. In the 'solve' function:
   - If the target sum is equal to 0 and the size of the current combination is equal to k, add the current combination to the vector of combinations.
   - If the current index is equal to the size of the array or the target sum is less than 0, return.
   - If the current number is less than or equal to the target sum:
     - Add the current number to the current combination.
     - Recursively call the 'solve' function with the updated index by incrementing it, the same number of elements to choose (k), the reduced target sum by subtracting the current number, the same array of available numbers (nums), the current combination, and the vector of combinations.
     - Remove the last added number from the current combination (backtracking).
   - Recursively call the 'solve' function with the updated index by incrementing it, the same number of elements to choose (k), the same target sum, the same array of available numbers (nums), the current combination, and the vector of combinations.
3. Create the main function called 'combinationSum3' that calculates and returns the vector of combinations.
   - Initialize an array of available numbers containing numbers from 1 to 9.
   - Initialize an empty vector to store the combinations.
   - Call the 'solve' function with the initial index as 0, the number of elements to choose (k), the target sum (n), the array of available numbers, an empty temporary vector, and the vector of combinations.
   - Return the vector of combinations.

Time Complexity: O(2^9), as there are 9 available numbers and we have to explore all possible combinations.
Space Complexity: O(k), as the maximum depth of the recursion tree is determined by the number of elements to choose (k).

CODE:*/
void solve(int i, int k, int tar, vector<int>& nums, vector<int>& temp, vector<vector<int>>& ans) {
    if (tar == 0 && temp.size() == k) {
        ans.push_back(temp);
        return;
    }

    if (i == nums.size() || tar < 0)
        return;

    if (nums[i] <= tar) {
        temp.push_back(nums[i]);
        solve(i + 1, k, tar - nums[i], nums, temp, ans);
        temp.pop_back();
    }

    solve(i + 1, k, tar, nums, temp, ans);
}

vector<vector<int>> combinationSum3(int k, int n) {
    vector<int> nums;
    for (int i = 1; i <= 9; i++) {
        nums.push_back(i);
    }

    vector<vector<int>> ans;
    vector<int> temp;
    solve(0, k, n, nums, temp, ans);
    return ans;
}

/*QUESTION:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

Approach:
To generate all combinations of well-formed parentheses, we can use a recursive approach. We can start with an empty string and keep track of the number of open parentheses and close parentheses used so far.
1. Create a helper function called 'solve' that takes a vector of strings, a string representing the current combination, the count of open parentheses, the count of close parentheses, and the total number of pairs of parentheses as parameters.
2. In the 'solve' function:
   - If both the counts of open parentheses and close parentheses are equal to the total number of pairs of parentheses, add the current combination to the vector of strings.
   - If the count of open parentheses is less than or equal to the total number of pairs of parentheses, recursively call 'solve' by appending an open parenthesis to the current combination and incrementing the count of open parentheses.
   - If the count of open parentheses is greater than the count of close parentheses, recursively call 'solve' by appending a close parenthesis to the current combination and incrementing the count of close parentheses.
3. Create the main function called 'generateParenthesis' that generates all combinations of well-formed parentheses using the 'solve' function.
   - Create an empty vector of strings to store the combinations.
   - Call the 'solve' function with an empty string, count of open parentheses as 0, count of close parentheses as 0, and the total number of pairs of parentheses as 'n'.
   - Return the vector of strings containing all the combinations.

Time Complexity: O(2^N * N), where N is the given number of pairs of parentheses.
Space Complexity: O(N), where N is the given number of pairs of parentheses (for the recursion stack and storing combinations).

CODE:*/

void solve(vector<string>& ans, string s, int open, int close, int n) {
    if (open == n && close == n){
        ans.push_back(s);
        return;
    }

    if (open <= n)
        solve(ans, s + '(', open + 1, close, n);
    if (open > close)
        solve(ans, s + ')', open, close + 1, n);
}

vector<string> generateParenthesis(int n) {
    vector<string> ans;
    solve(ans, "", 0, 0, n);
    return ans;
}

/*QUESTION:
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

Example:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Approach:
We can use a recursive backtracking approach to generate all possible letter combinations.
1. Create a helper function called 'solve' that takes the current index, the input string of digits, a temporary string to store the current combination, the vector to store all combinations, and a mapping vector that maps each digit to its corresponding letters.
2. In the 'solve' function:
   - If the current index is equal to the size of the input string, add the current combination to the vector of combinations and return.
   - Get the corresponding digit at the current index from the input string.
   - Iterate through the letters associated with the current digit:
     - Append the current letter to the temporary string.
     - Recursively call the 'solve' function with the updated index by incrementing it, the same input string of digits, the updated temporary string, the vector of combinations, and the mapping vector.
     - Remove the last added letter from the temporary string (backtracking).
3. Create the main function called 'letterCombinations' that calculates and returns the vector of combinations.
   - Check if the input string is empty. If so, return an empty vector.
   - Initialize a mapping vector that maps each digit to its corresponding letters.
   - Initialize an empty temporary string.
   - Initialize an empty vector to store the combinations.
   - Call the 'solve' function with the initial index as 0, the input string of digits, the temporary string, the vector of combinations, and the mapping vector.
   - Return the vector of combinations.

Time Complexity: O(3^N * 4^M), where N is the number of digits that map to 3 letters and M is the number of digits that map to 4 letters.
Space Complexity: O(N + M), where N is the number of digits that map to 3 letters and M is the number of digits that map to 4 letters.

CODE:*/
void solve(int index, string digits, string& temp, vector<string>& ans, vector<string>& mp) {
    if (index == digits.size()) {
        ans.push_back(temp);
        return;
    }

    int num = digits[index] - '0';
    for (int i = 0; i < mp[num].size(); i++) {
        temp.push_back(mp[num][i]);
        solve(index + 1, digits, temp, ans, mp);
        temp.pop_back();
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.empty())
        return {};

    vector<string> mp{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string temp = "";
    vector<string> ans;
    solve(0, digits, temp, ans, mp);
    return ans;
}

/*QUESTION:
Given a string consisting of lowercase English alphabets, the task is to find the number of distinct subsequences of the string. Note that the answer can be very large, so the output will be the answer modulo 10^9 + 7.

Example:
Input: s = "gfg"
Output: 7
Explanation: The seven distinct subsequences are "", "g", "f", "gf", "fg", "gg", and "gfg".

Approach:
To find the number of distinct subsequences, we can use a recursive approach with backtracking.
1. Create a set to store the distinct subsequences.
2. Create a helper function called 'solve' that takes the input string 's', the current index, and a temporary string as parameters.
3. In the 'solve' function:
   - If the current index is equal to the size of the input string 's', insert the temporary string into the set of distinct subsequences.
   - Otherwise, do the following:
     - Include the character at the current index in the temporary string by appending it.
     - Recursively call the 'solve' function with the updated temporary string and the next index.
     - Exclude the character at the current index from the temporary string.
     - Recursively call the 'solve' function with the updated temporary string and the next index.
4. Create the main function called 'distinctSubsequences' that calculates the number of distinct subsequences.
   - Initialize an empty string as the temporary string.
   - Call the 'solve' function with the input string 's', index 0, and the empty temporary string.
   - Return the size of the set of distinct subsequences modulo 10^9 + 7.

Time Complexity: O(2^N), where N is the length of the input string 's'.
Space Complexity: O(2^N), where N is the length of the input string 's' (for storing the distinct subsequences in the set).

CODE:*/
unordered_set<string> st;

void solve(string& s, int index, string& temp) {
    if (index == s.size()) {
        st.insert(temp);
        return;
    }

    // Include the character at the current index
    temp.push_back(s[index]);
    solve(s, index + 1, temp);

    // Exclude the character at the current index
    temp.pop_back();
    solve(s, index + 1, temp);
}

int distinctSubsequences(string s) {
    string temp = "";
    solve(s, 0, temp);
    return st.size() % (int)(1e9 + 7);
}

/*QUESTION:
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Approach:
We can use a recursive backtracking approach to generate all possible palindrome partitioning.
1. Create a helper function called 'solve' that takes the current index, the input string 's', a temporary vector to store the current partition, and the vector to store all partitions.
2. In the 'solve' function:
   - If the current index is greater than or equal to the size of the input string 's', add the current partition to the vector of partitions and return.
   - Iterate through all possible substrings starting from the current index to the end of the string.
   - Check if the current substring is a palindrome by using a helper function 'isPalindrome'.
   - If the current substring is a palindrome:
     - Add the current substring to the temporary partition vector.
     - Recursively call the 'solve' function with the updated index by incrementing it, the same input string 's', the updated temporary partition vector, and the vector of partitions.
     - Remove the last added substring from the temporary partition vector (backtracking).
3. Create the main function called 'partition' that calculates and returns the vector of partitions.
   - Initialize an empty vector to store the partitions.
   - Initialize an empty temporary vector to store the current partition.
   - Call the 'solve' function with the initial index as 0, the input string 's', the temporary partition vector, and the vector of partitions.
   - Return the vector of partitions.

Time Complexity: O(N * 2^N), where N is the length of the input string 's'. In the worst case, we can have 2^N possible partitions, and for each partition, we need to check if each substring is a palindrome, which takes O(N) time.
Space Complexity: O(N), where N is the length of the input string 's'. The space is used for storing the temporary partition vector and the vector of partitions.

CODE:*/
bool isPalindrome(string& palin){
    int i = 0, j = palin.size() - 1;
    while (i < j) {
        if (palin[i] != palin[j])
            return false;
        i++;
        j--;
    }
    return true;
}

void solve(int i, string& s, vector<string>& temp, vector<vector<string>>& ans) {
    if (i >= s.size()) {
        ans.push_back(temp);
        return;
    }

    for (int p = i; p < s.size(); p++) {
        string palin = s.substr(i, p - i + 1);
        if (isPalindrome(palin)) {
            temp.push_back(palin);
            solve(p + 1, s, temp, ans);
            temp.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> ans;
    vector<string> temp;
    solve(0, s, temp, ans);
    return ans;
}

/**
 * QUESTION: Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
 * 
 * Example:
 * Input: s = "leetcode", wordDict = ["leet","code"]
 * Output: true
 * Explanation: Return true because "leetcode" can be segmented as "leet code".
 *
 * Approach:
 * We can solve this problem using a recursive approach with backtracking.
 * 1. Start from the beginning of the string and try to find a word from the dictionary that matches a substring starting at the current index.
 * 2. If we find a match, recursively call the function on the remaining substring.
 * 3. Repeat this process until we reach the end of the string.
 * 4. If we can successfully break the string into words, we return true. Otherwise, we return false.
 *
 * Time Complexity: O(2^N), where N is the length of the string. In the worst case, we can have 2^N recursive calls.
 * Space Complexity: O(N), where N is the length of the string. The recursion stack can go up to N in the worst case.
 */

bool solve(int index, string& s, unordered_set<string>& dict) {
    if (index >= s.size()) {
        return true;
    }

    for (int i = index; i < s.size(); i++) {
        string temp = s.substr(index, i - index + 1);

        if (dict.find(temp) != dict.end() && solve(i + 1, s, dict)) {
            return true;
        }
    }

    return false;
}

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict;
    for (int i = 0; i < wordDict.size(); i++) {
        dict.insert(wordDict[i]);
    }
    return solve(0, s, dict);
}

/*QUESTION:
Given an m x n grid of characters board and a string word, return true if word exists in the grid.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false


Approach:
We can use a backtracking approach to solve this problem.
1. Create a helper function called 'solve' that takes the current row index, column index, letter index, the target word, and the board.
2. In the 'solve' function:
   - If the letter index is equal to the length of the target word, set the flag to true and return.
   - Check if the current cell value is equal to the target letter.
   - If it is, mark the current cell as visited (by changing its value to '!') and recursively call the 'solve' function for its neighboring cells (up, down, left, and right).
   - After the recursive call, restore the original value of the current cell.
3. Create the main function called 'exist' that calculates and returns true if the word exists in the grid, false otherwise.
   - Initialize a flag variable to false.
   - Iterate through each cell in the grid.
   - If the current cell value is equal to the first letter of the target word, mark the current cell as visited (by changing its value to '!') and call the 'solve' function with the current cell's coordinates, letter index as 1, the target word, and the board.
   - If the flag is true, return true (word exists in the grid).
   - If the loop completes without finding the word, return false.

Time Complexity: O(M * N * 4^L), where M is the number of rows, N is the number of columns in the grid, and L is the length of the target word. In the worst case, we traverse the entire grid for each letter in the target word, and we have 4 choices (up, down, left, right) at each step.
Space Complexity: O(L), where L is the length of the target word. The space is used for the recursive call stack.

CODE:*/

// Note:- I'm making recursive call only for the potential grids rather than making call for the all four to reduce unwanted calls,
// this makes code quite big but if you want to make it compact you could make call for all four cases and after call check if it's valid
// just check the code of rat in maze for shorter code

bool flag = false;

void solve(int i, int j, int ltr, string& word, vector<vector<char>>& board) {
    if (ltr == word.size()) {
        flag = true;
        return;
    }

    // left
    if (j - 1 >= 0 && board[i][j - 1] == word[ltr]) {
        board[i][j - 1] = '!';
        solve(i, j - 1, ltr + 1, word, board);
        board[i][j - 1] = word[ltr];
    }
    // right
    if (j + 1 < board[0].size() && board[i][j + 1] == word[ltr]) {
        board[i][j + 1] = '!';
        solve(i, j + 1, ltr + 1, word, board);
        board[i][j + 1] = word[ltr];
    }
    // top
    if (i - 1 >= 0 && board[i - 1][j] == word[ltr]) {
        board[i - 1][j] = '!';
        solve(i - 1, j, ltr + 1, word, board);
        board[i - 1][j] = word[ltr];
    }
    // bottom
    if (i + 1 < board.size() && board[i + 1][j] == word[ltr]) {
        board[i + 1][j] = '!';
        solve(i + 1, j, ltr + 1, word, board);
        board[i + 1][j] = word[ltr];
    }
}

bool exist(vector<vector<char>>& board, string word) {
    flag = false;

    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            if (board[i][j] == word[0]) {
                board[i][j] = '!';
                solve(i, j, 1, word, board);
                board[i][j] = word[0];
                if (flag)
                    return true;
            }
        }
    }
    return false;
}

/*QUESTION:
Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). Value 0 at a cell in the matrix represents that it is blocked and rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it.

Example 1:

Input:
N = 4
m[][] = {{1, 0, 0, 0},
         {1, 1, 0, 1}, 
         {1, 1, 0, 0},
         {0, 1, 1, 1}}
Output:
DDRDRR DRDDRR
Explanation:
The rat can reach the destination at 
(3, 3) from (0, 0) by two paths - DRDDRR 
and DDRDRR, when printed in sorted order 
we get DDRDRR DRDDRR.

Approach:
We can use a backtracking approach to find all possible paths.
1. Create a helper function called 'solve' that takes the current row index, column index, a string representing the current path, a vector of strings to store the paths, the matrix, and the size of the matrix.
2. In the 'solve' function:
   - If the current position is the destination (N-1, N-1), add the current path to the vector of paths and return.
   - Check if the current position is valid and not a blocked cell.
   - Mark the current position as visited (by setting its value to 0) to avoid revisiting it.
   - Recursively call the 'solve' function for the neighboring cells (left, right, up, down) with the updated path.
   - After the recursive calls, restore the original value of the current position to allow other paths to visit it.
3. Create the main function called 'findPath' that calculates and returns all possible paths from (0, 0) to (N-1, N-1).
   - If the source cell or the destination cell is blocked, return an empty vector.
   - Initialize an empty vector of strings to store the paths.
   - Call the 'solve' function with the initial position (0, 0), an empty path string, the vector of paths, the matrix, and the size of the matrix.
   - Return the vector of paths.

Time Complexity: O(3^(N^2)), where N is the size of the matrix. In the worst case, each cell can have three possible neighboring cells to explore.
Space Complexity: O(N^2), as we are using a vector of strings to store the paths.

CODE:*/
bool isValid(int i, int j, vector<vector<int>>& m, int n) {
    if (i < 0 || i >= n || j < 0 || j >= n || m[i][j] == 0)
        return false;
    return true;
}

void solve(int i, int j, string temp, vector<string>& ans, vector<vector<int>>& m, int n) {
    if (i == n - 1 && j == n - 1) {
        ans.push_back(temp);
        return;
    }

    if (!isValid(i, j, m, n))
        return;

    m[i][j] = 0;

    solve(i, j - 1, temp + 'L', ans, m, n);
    solve(i, j + 1, temp + 'R', ans, m, n);
    solve(i - 1, j, temp + 'U', ans, m, n);
    solve(i + 1, j, temp + 'D', ans, m, n);

    m[i][j] = 1;
}

vector<string> findPath(vector<vector<int>>& m, int n) {
    if (m[0][0] == 0 || m[n - 1][n - 1] == 0)
        return {};

    vector<string> ans;
    string temp = "";
    solve(0, 0, temp, ans, m, n);
    return ans;
}

/*QUESTION:
Given an undirected graph and an integer M. The task is to determine if the graph can be colored with at most M colors such that no two adjacent vertices of the graph are colored with the same color. Here coloring of a graph means the assignment of colors to all vertices. Print 1 if it is possible to colour vertices and 0 otherwise.

Approach:
We can solve this problem using backtracking.
1. Create a helper function called 'isPossible' that takes the graph, an array of colors assigned to vertices, the number of vertices, the color to be assigned, and the current vertex.
   - Iterate through all the adjacent vertices of the current vertex.
   - If an adjacent vertex is already colored with the same color, return false.
   - If there is no conflict, continue checking other adjacent vertices.
   - If all adjacent vertices have different colors or are uncolored, return true.
2. Create another helper function called 'solve' that takes the graph, the number of colors, the number of vertices, an array of colors assigned to vertices, and the current vertex.
   - If all vertices have been assigned colors, return true.
   - Iterate through all possible colors from 1 to M.
   - If it is possible to assign the current color to the current vertex without any conflict, assign the color and recursively call the 'solve' function for the next vertex.
   - If the 'solve' function returns true, return true.
   - If the 'solve' function returns false, try the next color.
   - If no color can be assigned to the current vertex without any conflict, return false.
3. Create the main function called 'graphColoring' that initializes an array of colors and calls the 'solve' function to check if it is possible to color the graph.
   - If the 'solve' function returns true, return true.
   - Otherwise, return false.

Time Complexity: O(M^N), where M is the number of colors and N is the number of vertices in the graph. In the worst case, we have to try all possible color combinations for all vertices.
Space Complexity: O(N), as we are using an array of colors to store the assigned colors for each vertex.

CODE:*/
bool isPossible(bool graph[101][101], int color[], int N, int col, int node) {
    for (int k = 0; k < N; k++) {
        if (k != node && graph[node][k] == 1 && color[k] == col)
            return false;
    }
    return true;
}

bool solve(bool graph[101][101], int m, int N, int color[], int node) {
    if (node == N)
        return true;

    for (int i = 1; i <= m; i++) {
        if (isPossible(graph, color, N, i, node)) {
            color[node] = i;
            if (solve(graph, m, N, color, node + 1))
                return true;
            color[node] = 0;
        }
    }
    return false;
}

bool graphColoring(bool graph[101][101], int m, int N) {
    int color[N];
    memset(color, 0, sizeof color);
    if (solve(graph, m, N, color, 0))
        return true;
    return false;
}

/**
 * Question: The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
 * Given an integer n, return all distinct solutions to the n-queens puzzle.
 *
Example 1:


Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

 * Approach:
 * 1. Use backtracking to solve the n-queens puzzle.
 * 2. Start with an empty chessboard and try placing queens in each row, ensuring that no two queens threaten each other.
 * 3. Use row, column, and diagonal constraints to validate the queen placements.
 * 4. If a valid configuration is found, add it to the list of solutions.
 *
 * Time Complexity: O(N!), where N is the input parameter representing the size of the chessboard.
 *   - In the worst case, there can be N! possible configurations to check.
 *   - However, with the pruning technique used in backtracking, the actual runtime is much less than N! in most cases.
 *
 * Space Complexity: O(N^2), where N is the input parameter representing the size of the chessboard.
 *   - The space is used to store the chessboard configuration and the auxiliary arrays for tracking the used columns and diagonals.
 */

unordered_map<int,bool>rowMap ;
unordered_map<int,bool>left_downMap;
unordered_map<int,bool>left_upMap;

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> ans;
    vector<string> board (n,string(n,'.'));
    solve(0,n,board,ans);
    return ans;
}

void solve(int col, int n, vector<string>& board, vector<vector<string>>& ans){

    if(col==n){
        ans.push_back(board);
        return;
    }

    for(int row = 0; row < n; row++){
        if(isValid(row,col,n)){
            // setting in maps
            rowMap[row] = true;
            left_downMap[row+col+n] = true;
            left_upMap[row-col+n] = true;

            // making recursive calls
            board[row][col] = 'Q';
            solve(col+1,n,board,ans);
            board[row][col] = '.';

            // unsetting in maps
            rowMap[row] = false;
            left_downMap[row+col+n] = false;
            left_upMap[row-col+n] = false;
        }
    }
}

bool isValid(int row, int col, int n){

    bool cnd1 = rowMap[row];
    bool cnd2 = left_upMap[row-col+n];
    bool cnd3 = left_downMap[row+col+n];

    return (cnd1 || cnd2 || cnd3)? false:true;
}