Author: devangini123

🌙 Problem Statement: Write a recursive function fact(n) that returns the factorial of a number n. Example: Input: 5 Process: (5 * 4 * 3 * 2 * 1) Output: 120 Concepts: Recursion: Repeatedly multiply n with fact (n-1). Base Case: fact(1) = 1. Recursive Case: n * fact(n – 1) Approach: If n == 1, return 1 (base case). Else, return n * fact(n – 1). Time & Space Complexity: Time Complexity: O(n) Space Complexity: O(n) recursive call stack JavaScript Python Java C++ C C# using System; class Program { static int Fact(int n) { if (n == 1)…

🌙 Problem Statement: Write a recursive function sum(n) that calculates the sum of all odd numbers in an array arr up to index n. Example: Input: [5, 2, 6, 1, 3] Odd Numbers: 5, 1, 3 Output: 9 Concepts: Recursion: Repeatedly check whether arr[n] is odd, and add it only if true true. Base Case: If n == 0, return arr[0] if it’s odd, otherwise 0. Recursive Case: Return (arr[n] if odd) + sum(n – 1). Approach: Check if arr[n] is odd. If yes, add it to recursive result of sum(n-1). Else, skip it and continue recursion. Time & Space…

🌙 Problem Statement: Write a function sum(n) that calculates the sum of all numbers in an array arr using recursion. It sums from index 0 to n. Example: Input: [5, 2, 6, 1, 3] Process: 5 + 2 + 6 + 1 + 3 = 17 Output: 17 Concepts: Recursion: The function keeps summing the element at index n and calls itself with n-1. Base Case: If n == 0, return the first element. Recursive Case: Return arr[n] + sum(n – 1). Approach: If n == 0, return arr[0]. Otherwise, return arr[n] + sum(n – 1). Time & Space Complexity:…

🌙 Problem Statement: Write a function sum(n) that calculates the sum of the first n natural numbers using recursion. Example: Input: 5 Process: 5 + 4 + 3 + 2 + 1 = 15 Output: 15 Concepts: Recursion: A technique where a function calls itself with a reduced subproblem. Base Case: Stops recursion to prevent infinite calls. Here, if n === 0, return 0. Recursive Case: Return n + sum(n – 1). Approach: Use recursion to reduce the problem. Base case: if n === 0, return 0. Recursive case:return n + sum(n-1). This keeps adding numbers until n reaches 0,…

🌙 Recursion Recursion is a technique where a function calls itself to solve a problem by breaking it down into smaller sub-problems. Base Condition: Every function call in recursion is stored in the call stack. If the recursion is too deep or has no base condition, the call stack keeps growing until memory is exhausted, causing a stack overflow error. A base condition is essential in recursion. It stops the recursion when a certain condition is met. Without it, recursion goes infinite and causes a stack overflow. if (num === 0) return;. Approach: Problem: Print numbers from n to 1…

🌙 Backtracking Recursive Algorithmic technique for solving problems incrementally by trying partial solutions and then abandoning them (backtracking) is they fail to satisfy constraints. Note: Exploring all possibility but being smart by abandoning wrong path early. Example: Like trying all the paths in max and going back if you hit a wall. When to use Backtracking ? You want to explore all combination/permutations/subsets. When there is a Clear way to validate a partial solution. Number of combinations is too large to brute force, so you abandon the invalid ones early. Basically, Backtracking optimise Recursion. Note: Try a choice -> work…

🌙 Problem Statement Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order. Example 1: Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]] Example 2: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Constraints 1 0 && nums[i] == nums[i-1] && !used[i-1]) continue; used[i] = true; path.add(nums[i]); backtrack(nums, used, path, result); path.remove(path.size() – 1); used[i] = false; } } } class Solution { public: vector permuteUnique(vector& nums) { vector result; sort(nums.begin(), nums.end()); vector path; vector used(nums.size(), false); backtrack(nums, used, path, result); return result; } void backtrack(vector& nums, vector& used, vector& path, vector& result) {…

🌙 Problem Statement Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example 1: Input: s = “aab” Output: [[“a”,”a”,”b”],[“aa”,”b”]] Example 2: Input: s = “a” Output: [[“a”]] Constraints 1 { if(!remainingString.length) { result.push([…path]); } for(let i=1; i

🌙 Problem Statement: Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. 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 Constraints m == board.length n = board[i].length 1 bool: m, n = len(board),…

🌙 Problem Statement: 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. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively. 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. Example 2: Input: n = 1 Output: [[“Q”]]…