Welcome to Recursion Backtracking CodeSnap

Recursion involves a function calling itself to solve smaller instances of the same problem, often seen in tasks like calculating Factorial or Fibonacci numbers. Backtracking is an algorithmic technique built upon recursion for solving problems incrementally, typically exploring potential solutions and 'backtracking' (undoing choices) when a path proves invalid or unfruitful. It's commonly used for constraint satisfaction problems (N-Queens, Sudoku), finding permutations, combinations, subsets, or exploring paths (Word Search, Generate Parentheses). These techniques often involve exploring a state space tree.

Table of Contents

• Factorial of a Number

  Calculate the factorial of a non-negative integer n (denoted as n!), which is the product of all positive integers less than or equal to n. Base case is 0! = 1. Often implemented recursively.

• Fibonacci Sequence

  Compute the n-th Fibonacci number, where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Naive recursion is simple but inefficient; often requires memoization or dynamic programming for optimization.

• Power of a Number (x^n)

  Implement pow(x, n), which calculates x raised to the power n (x^n). Can be solved efficiently using recursion and the principle of exponentiation by squaring.

• Permutations of a String

  Generate all possible unique permutations (rearrangements of characters) of a given input string. This is a classic backtracking problem.

• Permutations of an Array

  Given an array `nums` of distinct integers, return all possible permutations (orderings) of the elements. Solved using backtracking.

• Generate Parentheses

  Given n pairs of parentheses, generate all combinations of well-formed (valid) parentheses strings. Uses backtracking to ensure parentheses are balanced.

• Letter Combinations of Phone Number

  Given a string containing digits 2-9, return all possible letter combinations mapped from a standard phone keypad. Uses backtracking to explore combinations.

• Word Search in 2D Board

  Given an m x n grid of characters and a word, determine if the word exists in the grid by moving horizontally or vertically to adjacent cells. The same cell cannot be used more than once. Solved with DFS/backtracking.

• N-Queens Problem

  Place N queens on an N×N chessboard such that no two queens attack each other (same row, column, or diagonal). Find all distinct solutions or configurations. A classic backtracking problem.

• Sudoku Solver

  Write a function to solve a Sudoku puzzle by filling the empty cells ('.') with digits 1-9, following Sudoku rules. Assumes a unique solution exists. Uses backtracking with constraint checking.

• Subset Sum Problem

  Given a set of non-negative integers and a target sum, determine if there is a subset of the given set whose elements sum up to the target sum. Can be solved using recursion/backtracking or dynamic programming.

• Combinations (k out of n)

  Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. The order of elements within a combination doesn't matter.

• Palindrome Partitioning

  Given a string s, partition s such that every substring in the partition is a palindrome. Return all possible palindrome partitionings of s. Uses backtracking, often combined with palindrome checks.