DSA: Problems on Recursion, Pointers, and Dynamic Allocation

Reverse a String: Write a recursive C program to reverse a given string. The program should take a string as input and return its reverse.
Fibonacci Sequence: Write a recursive C program to find the n-th number in the Fibonacci sequence, utilizing memoization to optimize performance. The program should take an integer n as input and output the n-th Fibonacci number. Memoization should be implemented by storing previously calculated Fibonacci numbers to avoid redundant calculations and improve efficiency.
Subset Sum Problem: Write a recursive C program to determine if there is a subset of a given set with a sum equal to a given target. The input should be an array of integers and the target sum.
N-Queens Problem: Write a recursive C program to solve the N-Queens problem. Given an integer N, place N queens on an ( N x N ) chessboard so that no two queens threaten each other.
All Possible Permutations: Write a recursive C program to generate all possible permutations of a given array of distinct integers.
Partition Problem: Write a recursive C program to determine if a given array can be partitioned into two subsets such that the sum of elements in both subsets is the same.
Word Search: Write a recursive C program to determine if a given word exists in a 2D grid of characters. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring.
Dynamic Memory Allocation and Deallocation: Write a C program that dynamically allocates memory for an array of integers, fills it with values, and then deallocates the memory. Use both pointers and double pointers to manage the memory.
Dynamic Array of Strings: Write a C program to create a dynamic array of strings using pointers to pointers. Implement functions to add, remove, and search for strings within the array.

Hints

Reverse a String: Start by writing a function that takes the string, the starting index, and the ending index as parameters. Swap the characters at the starting and ending indices, then recursively call the function with the next inner indices. The base case is when the starting index is greater than or equal to the ending index.
Fibonacci Sequence: Initialize an array to store the Fibonacci numbers. Write a recursive function that takes an integer ( n ) and the memoization array as parameters. The base cases are for ( n = 0 ) and ( n = 1 ). For other values, if the result is already in the memoization array, return it. Otherwise, compute the Fibonacci number recursively, store it in the array, and return it.
Subset Sum Problem: Write a recursive function that takes the array, its size, and the target sum as parameters. The base cases are when the target sum is 0 (return true) or the array size is 0 (return false). For each element, check if the target can be achieved by including or excluding the current element, and recursively solve for the remaining elements and the reduced target.
N-Queens Problem: Use a recursive backtracking approach. Write a function to place queens one by one in different rows, starting from the leftmost column. For each column, check if placing the queen in the current row does not threaten any previously placed queens. If placing the queen is safe, mark the position and recursively place the rest of the queens. If a solution is found, return true; otherwise, backtrack and try the next row.
All Possible Permutations: Write a recursive function that generates permutations by swapping elements. Start with the first element and recursively generate permutations for the rest of the array by swapping each subsequent element with the current element. Use a helper function to swap elements and ensure the original array is restored before the next iteration.
Partition Problem: Calculate the total sum of the array. If the sum is odd, it's impossible to partition it into two equal subsets. Otherwise, write a recursive function to check if there is a subset with a sum equal to half of the total sum. Use a similar approach to the Subset Sum Problem, where you include or exclude elements and check for the target sum.
Word Search: Write a recursive function to search for the word in the grid. Start from each cell and recursively check if the word can be constructed by moving to adjacent cells. Use a visited array to mark cells as visited and backtrack if the word cannot be constructed from the current path. Ensure that the function checks all possible directions (up, down, left, right).
Dynamic Memory Allocation and Deallocation: Use malloc to allocate memory for an integer array. Write functions to fill the array with values, print its elements, and deallocate the memory using free. Use a double pointer to handle the array in the main function and pass it to the functions for allocation and deallocation.
Dynamic Array of Strings: Use malloc to allocate memory for an array of character pointers. Write functions to add, remove, and search for strings. Use a double pointer for the dynamic array and handle memory allocation and reallocation within these functions. Ensure proper memory management by deallocating memory when strings are removed.

Solutions and Explanation:

Reverse a String:

 #include <stdio.h>
 #include <string.h>

 // Function to reverse a string using recursion
 void reverseString(char str[], int start, int end) {
     // Base case: if start index is greater than or equal to end index
     if (start >= end) {
         return;
     }

     // Swap the characters at start and end indices
     char temp = str[start];
     str[start] = str[end];
     str[end] = temp;

     // Recursive call with updated indices
     reverseString(str, start + 1, end - 1);
 }

 int main() {
     char str[] = "Hello, World!";
     int length = strlen(str);

     // Reverse the string
     reverseString(str, 0, length - 1);

     // Print the reversed string
     printf("Reversed String: %s\n", str);

     return 0;
 }

Function Definition:
- The function reverseString takes a string str, and two integers start and end as parameters.
- start is the starting index, and end is the ending index of the string.
Base Case:
- The base case for the recursion is when start is greater than or equal to end. At this point, the function returns without making further recursive calls, as the string is fully reversed.
Swapping Characters:
- The characters at the start and end indices are swapped.
Recursive Call:
- The function calls itself with updated indices: start + 1 and end - 1, to move towards the middle of the string.
Main Function:
- The main function initializes a string str with the value "Hello, World!" and calculates its length.
- It calls the reverseString function to reverse the string.
- Finally, it prints the reversed string.

Let's walk through the process with an example string "ABCDEF":

    Original String: "ABCDEF"

    Step 1: Swap 'A' and 'F'
    A B C D E F
    ^         ^
    F B C D E A

    Step 2: Swap 'B' and 'E'
    F B C D E A
      ^     ^
    F E C D B A

    Step 3: Swap 'C' and 'D'
    F E C D B A
        ^ ^
    F E D C B A

    Final reversed string: "FEDCBA"

Each step involves swapping the characters at the current start and end indices and then recursively calling the function with the updated indices. The recursion continues until the start index is no longer less than the end index, which indicates that the entire string has been reversed.

Fibonacci Sequence:

 #include <stdio.h>
 #include <stdlib.h>

 // Function to initialize memoization array with -1
 void initializeMemo(int memo[], int size) {
     for (int i = 0; i < size; i++) {
         memo[i] = -1;
     }
 }

 // Recursive function to find n-th Fibonacci number using memoization
 int fibonacci(int n, int memo[]) {
     // Base cases
     if (n <= 1) {
         return n;
     }

     // Check if value is already computed
     if (memo[n] != -1) {
         return memo[n];
     }

     // Recursive calculation with memoization
     memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);

     return memo[n];
 }

 int main() {
     int n;

     printf("Enter the position n to find the n-th Fibonacci number: ");
     scanf("%d", &n);

     // Allocate memory for memoization array
     int *memo = (int *)malloc((n + 1) * sizeof(int));
     initializeMemo(memo, n + 1);

     // Get the n-th Fibonacci number
     int result = fibonacci(n, memo);

     // Print the result
     printf("The %d-th Fibonacci number is: %d\n", n, result);

     // Free allocated memory
     free(memo);

     return 0;
 }

Initialization Function:
- The initializeMemo function sets all elements of the memoization array to -1, indicating that no Fibonacci numbers have been computed yet.
Fibonacci Function:
- The fibonacci function takes an integer n and the memoization array memo as parameters.
- Base Cases: If n is 0 or 1, it returns n (the 0th Fibonacci number is 0, and the 1st Fibonacci number is 1).
- Memoization Check: It checks if the Fibonacci number for n has already been computed and stored in memo[n]. If so, it returns the stored value.
- Recursive Calculation: If the value is not already computed, it calculates the Fibonacci number recursively and stores the result in memo[n].
Main Function:
- The main function prompts the user to enter the position n for which the Fibonacci number is to be found.
- It allocates memory for the memoization array and initializes it.
- It calls the fibonacci function to compute the n-th Fibonacci number and prints the result.
- Finally, it frees the allocated memory.

Let's walk through the process for calculating the 5th Fibonacci number with memoization:

    Initial Memo Array: [-1, -1, -1, -1, -1, -1]

    Step 1: fibonacci(5)
      - Not in memo, so calculate fibonacci(4) + fibonacci(3)

    Step 2: fibonacci(4)
      - Not in memo, so calculate fibonacci(3) + fibonacci(2)

    Step 3: fibonacci(3)
      - Not in memo, so calculate fibonacci(2) + fibonacci(1)

    Step 4: fibonacci(2)
      - Not in memo, so calculate fibonacci(1) + fibonacci(0)

    Step 5: fibonacci(1) = 1 (base case)
      - Memo Array: [-1, 1, -1, -1, -1, -1]

    Step 6: fibonacci(0) = 0 (base case)
      - Memo Array: [0, 1, -1, -1, -1, -1]

    Step 7: fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1
      - Memo Array: [0, 1, 1, -1, -1, -1]

    Step 8: fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
      - Memo Array: [0, 1, 1, 2, -1, -1]

    Step 9: fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + 1 = 3
      - Memo Array: [0, 1, 1, 2, 3, -1]

    Step 10: fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5
      - Memo Array: [0, 1, 1, 2, 3, 5]

    Final result: The 5th Fibonacci number is 5

Each step involves either returning a previously computed value from the memoization array or calculating a new Fibonacci number recursively and storing it in the memoization array for future use. This reduces redundant calculations and optimizes the performance of the program.

Subset Sum Problem:

 #include <stdio.h>
 #include <stdbool.h>

 // Function to check if there is a subset with a given sum
 bool isSubsetSum(int set[], int n, int sum) {
     // Base Cases
     if (sum == 0) {
         return true;
     }
     if (n == 0 && sum != 0) {
         return false;
     }

     // If last element is greater than sum, ignore it
     if (set[n - 1] > sum) {
         return isSubsetSum(set, n - 1, sum);
     }

     // Check if sum can be obtained by any of the following:
     // (a) including the last element
     // (b) excluding the last element
     return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
 }

 int main() {
     int set[] = {3, 34, 4, 12, 5, 2};
     int sum = 9;
     int n = sizeof(set) / sizeof(set[0]);

     if (isSubsetSum(set, n, sum)) {
         printf("Found a subset with the given sum\n");
     } else {
         printf("No subset with the given sum\n");
     }

     return 0;
 }

Function Definition:
- The isSubsetSum function takes an array set, the size of the array n, and the target sum sum as parameters.
- Base Cases:
  - If sum is 0, it returns true, as the empty subset has a sum of 0.
  - If n is 0 and sum is not 0, it returns false, as no subset can be formed from an empty set.
- Ignoring Elements:
  - If the last element of the set is greater than the target sum, it is ignored, and the function is called recursively with the remaining elements.
- Recursive Cases:
  - The function checks if the sum can be obtained either by including or excluding the last element of the set.
Main Function:
- The main function initializes an array set with some integers and a target sum sum.
- It calculates the size of the array n and calls the isSubsetSum function to check if a subset with the given sum exists.
- It prints the result based on the return value of the isSubsetSum function.

Let's walk through the process for finding a subset with the sum of 9 in the set {3, 34, 4, 12, 5, 2}:

    Initial Set: {3, 34, 4, 12, 5, 2}, Sum: 9

    Step 1: Check last element 2
      - Include 2: New Sum = 7
      - Exclude 2: Sum remains 9

    Step 2: Check next element 5 (include 2)
      - Include 5: New Sum = 2
      - Exclude 5: Sum remains 7

    Step 3: Check next element 12 (include 5)
      - Include 12: New Sum = -10 (ignore as negative)
      - Exclude 12: Sum remains 2

    Step 4: Check next element 4 (exclude 12)
      - Include 4: New Sum = -2 (ignore as negative)
      - Exclude 4: Sum remains 2

    Step 5: Check next element 34 (exclude 4)
      - Include 34: New Sum = -32 (ignore as negative)
      - Exclude 34: Sum remains 2

    Step 6: Check next element 3 (exclude 34)
      - Include 3: New Sum = -1 (ignore as negative)
      - Exclude 3: Sum remains 2

    Step 7: Check remaining element (no elements left)
      - Base Case: Sum is 0 or not (it is not 0)

    Step 8: Backtrack to exclude 5 (with 2)
      - New Sum = 7, Check next element 12

    Step 9: Check next element 12 (exclude 5)
      - Include 12: New Sum = -5 (ignore as negative)
      - Exclude 12: Sum remains 7

    Step 10: Check next element 4 (exclude 12)
      - Include 4: New Sum = 3
      - Exclude 4: Sum remains 7

    Step 11: Check next element 34 (exclude 4)
      - Include 34: New Sum = -27 (ignore as negative)
      - Exclude 34: Sum remains 3

    Step 12: Check next element 3 (include 4)
      - Include 3: New Sum = 0 (found a subset)
      - Exclude 3: Sum remains 3

    Found a subset with the given sum: {4, 5, 2}

N-Queens Problem:

 #include <stdio.h>
 #include <stdbool.h>

 // Function to print the chessboard
 void printSolution(int board[], int N) {
     for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
             if (board[i] == j) {
                 printf("Q ");
             } else {
                 printf(". ");
             }
         }
         printf("\n");
     }
     printf("\n");
 }

 // Function to check if a queen can be placed on board[row][col]
 bool isSafe(int board[], int row, int col, int N) {
     for (int i = 0; i < row; i++) {
         if (board[i] == col || abs(board[i] - col) == abs(i - row)) {
             return false;
         }
     }
     return true;
 }

 // Recursive function to solve N-Queens problem
 bool solveNQueens(int board[], int row, int N) {
     // Base case: If all queens are placed
     if (row == N) {
         printSolution(board, N);
         return true;
     }

     // Consider this row and try placing this queen in all columns one by one
     bool res = false;
     for (int col = 0; col < N; col++) {
         // Check if the queen can be placed on board[row][col]
         if (isSafe(board, row, col, N)) {
             board[row] = col;

             // Make result true if any placement is possible
             res = solveNQueens(board, row + 1, N) || res;

             // No need to reset the board[row] as we are overwriting it in the next iteration
         }
     }
     return res;
 }

 int main() {
     int N;

     printf("Enter the value of N for the N-Queens problem: ");
     scanf("%d", &N);

     // Create an array to store the column positions of queens
     int board[N];

     if (!solveNQueens(board, 0, N)) {
         printf("Solution does not exist\n");
     }

     return 0;
 }

Print Solution Function:
- The printSolution function prints the chessboard configuration where queens are placed. Queens are represented by 'Q' and empty spaces by '.'.
Is Safe Function:
- The isSafe function checks if a queen can be placed at board[row][col] without being threatened by other queens. It checks:
  - If there is no queen in the same column.
  - If there is no queen in the same diagonal.
Solve N-Queens Function:
- The solveNQueens function recursively tries to place queens on the board.
- Base Case: If all queens are placed (row == N), it prints the solution and returns true.
- It iterates through each column in the current row and checks if placing a queen at board[row][col] is safe.
- If safe, it places the queen and recursively attempts to place the next queen in the next row.
- If a placement is possible, it sets the result to true.
Main Function:
- The main function prompts the user to enter the value of N and initializes the board array.
- It calls the solveNQueens function to solve the problem and prints the result.

Let's walk through the process for solving the 4-Queens problem:

    Initial Board: (Empty)

    Step 1: Place queen in row 0, col 0
    Q . . .
    . . . .
    . . . .
    . . . .

    Step 2: Place queen in row 1, col 2
    Q . . .
    . . Q .
    . . . .
    . . . .

    Step 3: Place queen in row 2, col 3 (Backtrack, col 3 is not safe)
    Step 4: Place queen in row 1, col 3 (Backtrack, col 3 is not safe)

    Backtrack to row 0, col 0
    Q . . .
    . . . .
    . . . .
    . . . .

    Step 5: Place queen in row 0, col 1
    . Q . .
    . . . .
    . . . .
    . . . .

    Step 6: Place queen in row 1, col 3
    . Q . .
    . . . Q
    . . . .
    . . . .

    Step 7: Place queen in row 2, col 0
    . Q . .
    . . . Q
    Q . . .
    . . . .

    Step 8: Place queen in row 3, col 2
    . Q . .
    . . . Q
    Q . . .
    . . Q .

    Solution Found:
    . Q . .
    . . . Q
    Q . . .
    . . Q .

    Backtrack to row 2, col 0
    . Q . .
    . . . Q
    . . . .
    . . . .

    Backtrack to row 1, col 3
    . Q . .
    . . . .
    . . . .
    . . . .

    Step 9: Place queen in row 0, col 2
    . . Q .
    . . . .
    . . . .
    . . . .

    Step 10: Place queen in row 1, col 0
    . . Q .
    Q . . .
    . . . .
    . . . .

    Step 11: Place queen in row 2, col 3
    . . Q .
    Q . . .
    . . . Q
    . . . .

    Step 12: Place queen in row 3, col 1
    . . Q .
    Q . . .
    . . . Q
    . Q . .

    Solution Found:
    . . Q .
    Q . . .
    . . . Q
    . Q . .

The program explores different configurations by placing queens row by row and backtracking when it encounters a conflict. It continues this process until it finds all possible solutions or determines that no solution exists.

All Possible Permutations:

 #include <stdio.h>

 // Function to swap two integers
 void swap(int *a, int *b) {
     int temp = *a;
     *a = *b;
     *b = temp;
 }

 // Function to print an array
 void printArray(int arr[], int size) {
     for (int i = 0; i < size; i++) {
         printf("%d ", arr[i]);
     }
     printf("\n");
 }

 // Recursive function to generate all permutations
 void generatePermutations(int arr[], int start, int end) {
     if (start == end) {
         printArray(arr, end + 1);
         return;
     }

     for (int i = start; i <= end; i++) {
         // Swap the current element with the start element
         swap(&arr[start], &arr[i]);

         // Recurse for the next position
         generatePermutations(arr, start + 1, end);

         // Backtrack: swap back the elements to their original positions
         swap(&arr[start], &arr[i]);
     }
 }

 int main() {
     int arr[] = {1, 2, 3};
     int n = sizeof(arr) / sizeof(arr[0]);

     printf("All possible permutations of the array are:\n");
     generatePermutations(arr, 0, n - 1);

     return 0;
 }

Swap Function:
- The swap function swaps the values of two integers.
Print Array Function:
- The printArray function prints the elements of an array.
Generate Permutations Function:
- The generatePermutations function takes an array arr, a starting index start, and an ending index end.
- Base Case: If start is equal to end, it means a permutation is formed, and it prints the array.
- The function iterates through the array, swapping the start element with each element from start to end.
- It recursively calls itself to generate permutations for the next position.
- After the recursive call, it swaps back the elements to their original positions to backtrack and explore other permutations.
Main Function:
- The main function initializes an array arr with some integers and calculates its size n.
- It calls the generatePermutations function to generate all permutations and prints the result.

Let's walk through the process for generating all permutations of the array {1, 2, 3}:

    Initial Array: {1, 2, 3}

    Step 1: start = 0, i = 0
    Swap(1, 1)
    Array: {1, 2, 3}
    Recursive call with start = 1

    Step 2: start = 1, i = 1
    Swap(2, 2)
    Array: {1, 2, 3}
    Recursive call with start = 2

    Step 3: start = 2, i = 2
    Swap(3, 3)
    Array: {1, 2, 3}
    Base case reached, print: 1 2 3

    Backtrack: Swap(3, 3)
    Array: {1, 2, 3}

    Step 4: start = 1, i = 2
    Swap(2, 3)
    Array: {1, 3, 2}
    Recursive call with start = 2

    Step 5: start = 2, i = 2
    Swap(2, 2)
    Array: {1, 3, 2}
    Base case reached, print: 1 3 2

    Backtrack: Swap(2, 3)
    Array: {1, 2, 3}

    Backtrack: Swap(1, 1)
    Array: {1, 2, 3}

    Step 6: start = 0, i = 1
    Swap(1, 2)
    Array: {2, 1, 3}
    Recursive call with start = 1

    Step 7: start = 1, i = 1
    Swap(1, 1)
    Array: {2, 1, 3}
    Recursive call with start = 2

    Step 8: start = 2, i = 2
    Swap(3, 3)
    Array: {2, 1, 3}
    Base case reached, print: 2 1 3

    Backtrack: Swap(3, 3)
    Array: {2, 1, 3}

    Step 9: start = 1, i = 2
    Swap(1, 3)
    Array: {2, 3, 1}
    Recursive call with start = 2

    Step 10: start = 2, i = 2
    Swap(1, 1)
    Array: {2, 3, 1}
    Base case reached, print: 2 3 1

    Backtrack: Swap(1, 3)
    Array: {2, 1, 3}

    Backtrack: Swap(2, 1)
    Array: {1, 2, 3}

    Step 11: start = 0, i = 2
    Swap(1, 3)
    Array: {3, 2, 1}
    Recursive call with start = 1

    Step 12: start = 1, i = 1
    Swap(2, 2)
    Array: {3, 2, 1}
    Recursive call with start = 2

    Step 13: start = 2, i = 2
    Swap(1, 1)
    Array: {3, 2, 1}
    Base case reached, print: 3 2 1

    Backtrack: Swap(1, 1)
    Array: {3, 2, 1}

    Step 14: start = 1, i = 2
    Swap(2, 1)
    Array: {3, 1, 2}
    Recursive call with start = 2

    Step 15: start = 2, i = 2
    Swap(2, 2)
    Array: {3, 1, 2}
    Base case reached, print: 3 1 2

    Backtrack: Swap(2, 1)
    Array: {3, 2, 1}

    Backtrack: Swap(3, 1)
    Array: {1, 2, 3}

    All permutations printed: 
    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 2 1
    3 1 2

Each step involves swapping the elements and recursively generating permutations for the remaining positions. The function backtracks after each recursive call to restore the array to its original state before exploring other permutations. This process continues until all permutations are generated and printed.

Partition Problem:

 #include <stdio.h>
 #include <stdbool.h>

 // Function to check if there is a subset with a given sum
 bool isSubsetSum(int set[], int n, int sum) {
     // Base Cases
     if (sum == 0) {
         return true;
     }
     if (n == 0 && sum != 0) {
         return false;
     }

     // If last element is greater than sum, ignore it
     if (set[n - 1] > sum) {
         return isSubsetSum(set, n - 1, sum);
     }

     // Check if sum can be obtained by any of the following:
     // (a) including the last element
     // (b) excluding the last element
     return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
 }

 // Function to check if the array can be partitioned into two subsets of equal sum
 bool canPartition(int set[], int n) {
     int sum = 0;

     // Calculate the total sum of the array
     for (int i = 0; i < n; i++) {
         sum += set[i];
     }

     // If sum is odd, partition is not possible
     if (sum % 2 != 0) {
         return false;
     }

     // Check if there is a subset with sum equal to half of total sum
     return isSubsetSum(set, n, sum / 2);
 }

 int main() {
     int set[] = {1, 5, 11, 5};
     int n = sizeof(set) / sizeof(set[0]);

     if (canPartition(set, n)) {
         printf("The array can be partitioned into two subsets of equal sum.\n");
     } else {
         printf("The array cannot be partitioned into two subsets of equal sum.\n");
     }

     return 0;
 }

Is Subset Sum Function:
- The isSubsetSum function takes an array set, the size of the array n, and the target sum sum.
- Base Cases:
  - If sum is 0, it returns true, as the empty subset has a sum of 0.
  - If n is 0 and sum is not 0, it returns false, as no subset can be formed from an empty set.
- Ignoring Elements:
  - If the last element of the set is greater than the target sum, it is ignored, and the function is called recursively with the remaining elements.
- Recursive Cases:
  - The function checks if the sum can be obtained either by including or excluding the last element of the set.
Can Partition Function:
- The canPartition function takes an array set and its size n.
- It calculates the total sum of the array.
- If the total sum is odd, it returns false because it's impossible to partition the array into two subsets of equal sum.
- If the total sum is even, it calls the isSubsetSum function to check if there is a subset with a sum equal to half of the total sum.
Main Function:
- The main function initializes an array set with some integers and calculates its size n.
- It calls the canPartition function to check if the array can be partitioned into two subsets of equal sum and prints the result.

Let's walk through the process for checking if the array {1, 5, 11, 5} can be partitioned into two subsets of equal sum:

    Initial Array: {1, 5, 11, 5}
    Total Sum: 1 + 5 + 11 + 5 = 22

    Step 1: Total sum is even (22), so partition might be possible.
    Target Sum for each subset: 22 / 2 = 11

    Step 2: Check if there is a subset with sum 11
    - Initial call: isSubsetSum({1, 5, 11, 5}, 4, 11)

    Step 3: Check last element 5
    - Include 5: New Sum = 6
    - Exclude 5: Sum remains 11

    Step 4: Check next element 11 (Exclude 5)
    - Include 11: New Sum = 0 (Subset found)
    - Exclude 11: Sum remains 11

    Subset with sum 11 found: {11}

    The array can be partitioned into two subsets of equal sum.

Each step involves checking whether the current element should be included in the subset or not. The function recursively explores both possibilities and backtracks when necessary. The recursion continues until a subset with the desired sum is found or all possibilities are exhausted. The main function then determines if the array can be partitioned into two equal subsets based on the result of the subset sum check.

Word Search:

 #include <stdio.h>
 #include <stdbool.h>

 // Define the number of rows and columns
 #define ROWS 4
 #define COLS 4

 // Directions for moving in the grid
 int rowDir[] = {-1, 1, 0, 0};
 int colDir[] = {0, 0, -1, 1};

 // Function to check if a cell is within the grid and not visited
 bool isValid(int row, int col, bool visited[ROWS][COLS]) {
     return (row >= 0 && row < ROWS && col >= 0 && col < COLS && !visited[row][col]);
 }

 // Recursive function to search for the word in the grid
 bool searchWord(char grid[ROWS][COLS], bool visited[ROWS][COLS], int row, int col, const char *word, int index) {
     // Base case: if the entire word is found
     if (word[index] == '\0') {
         return true;
     }

     // Check if the current cell is valid and matches the current character
     if (isValid(row, col, visited) && grid[row][col] == word[index]) {
         // Mark the current cell as visited
         visited[row][col] = true;

         // Recur for all possible directions
         for (int i = 0; i < 4; i++) {
             int newRow = row + rowDir[i];
             int newCol = col + colDir[i];
             if (searchWord(grid, visited, newRow, newCol, word, index + 1)) {
                 return true;
             }
         }

         // Backtrack: unmark the current cell
         visited[row][col] = false;
     }

     return false;
 }

 // Function to search for the word in the entire grid
 bool wordExists(char grid[ROWS][COLS], const char *word) {
     bool visited[ROWS][COLS] = {false};

     // Start from each cell in the grid
     for (int row = 0; row < ROWS; row++) {
         for (int col = 0; col < COLS; col++) {
             if (searchWord(grid, visited, row, col, word, 0)) {
                 return true;
             }
         }
     }

     return false;
 }

 int main() {
     char grid[ROWS][COLS] = {
         {'A', 'B', 'C', 'E'},
         {'S', 'F', 'C', 'S'},
         {'A', 'D', 'E', 'E'},
         {'A', 'B', 'E', 'E'}
     };

     const char *word = "ABCCED";

     if (wordExists(grid, word)) {
         printf("The word \"%s\" exists in the grid.\n", word);
     } else {
         printf("The word \"%s\" does not exist in the grid.\n", word);
     }

     return 0;
 }

Is Valid Function:
- The isValid function checks if a cell is within the grid and not visited. It returns true if the cell is within bounds and not visited, otherwise false.
Search Word Function:
- The searchWord function recursively searches for the word in the grid.
- Base Case: If the entire word is found (i.e., word[index] is '\0'), it returns true.
- It checks if the current cell is valid and matches the current character of the word.
- If valid, it marks the current cell as visited.
- It recursively searches in all four possible directions (up, down, left, right) for the next character in the word.
- If the word is found in any direction, it returns true.
- If not found, it backtracks by unmarking the current cell.
Word Exists Function:
- The wordExists function searches for the word in the entire grid.
- It initializes a visited array to keep track of visited cells.
- It starts the search from each cell in the grid by calling the searchWord function.
- If the word is found starting from any cell, it returns true. Otherwise, it returns false.
Main Function:
- The main function initializes a grid with characters and a word to search.
- It calls the wordExists function to check if the word exists in the grid and prints the result.

Let's walk through the process for searching the word "ABCCED" in the grid:

    Initial Grid:
    A B C E
    S F C S
    A D E E
    A B E E

    Word to Search: "ABCCED"

    Start from cell (0,0):
    A B C E
    S F C S
    A D E E
    A B E E
    ^
    Index 0: Matches 'A'

    Move to cell (0,1):
    A B C E
    S F C S
    A D E E
    A B E E
      ^
    Index 1: Matches 'B'

    Move to cell (0,2):
    A B C E
    S F C S
    A D E E
    A B E E
        ^
    Index 2: Matches 'C'

    Move to cell (1,2):
    A B C E
    S F C S
    A D E E
    A B E E
        ^
    Index 3: Matches 'C'

    Move to cell (2,2):
    A B C E
    S F C S
    A D E E
    A B E E
          ^
    Index 4: Matches 'E'

    Move to cell (2,1):
    A B C E
    S F C S
    A D E E
    A B E E
      ^
    Index 5: Matches 'D'

    Entire word "ABCCED" found in the grid.

The function recursively checks each cell and explores all possible directions (up, down, left, right) while keeping track of visited cells to avoid revisiting. It backtracks if a path does not lead to the complete word and continues to explore other paths until the word is found or all possibilities are exhausted.

Dynamic Memory Allocation and Deallocation:

 #include <stdio.h>
 #include <stdlib.h>

 // Function to allocate memory for an integer array
 void allocateArray(int **arr, int size) {
     *arr = (int *)malloc(size * sizeof(int));
     if (*arr == NULL) {
         printf("Memory allocation failed\n");
         exit(1);
     }
 }

 // Function to fill the array with values
 void fillArray(int *arr, int size) {
     for (int i = 0; i < size; i++) {
         arr[i] = i + 1; // Fill the array with values 1, 2, 3, ...
     }
 }

 // Function to print the elements of the array
 void printArray(int *arr, int size) {
     for (int i = 0; i < size; i++) {
         printf("%d ", arr[i]);
     }
     printf("\n");
 }

 // Function to deallocate the memory of the array
 void deallocateArray(int **arr) {
     free(*arr);
     *arr = NULL; // Set the pointer to NULL after freeing the memory
 }

 int main() {
     int *array = NULL;
     int size;

     printf("Enter the size of the array: ");
     scanf("%d", &size);

     // Allocate memory for the array
     allocateArray(&array, size);

     // Fill the array with values
     fillArray(array, size);

     // Print the elements of the array
     printf("Array elements: ");
     printArray(array, size);

     // Deallocate the memory of the array
     deallocateArray(&array);

     if (array == NULL) {
         printf("Memory successfully deallocated\n");
     } else {
         printf("Memory deallocation failed\n");
     }

     return 0;
 }

Allocate Array Function:
- The allocateArray function takes a double pointer arr and an integer size.
- It allocates memory for the array using malloc and assigns the allocated memory to the pointer arr.
- If memory allocation fails, it prints an error message and exits the program.
Fill Array Function:
- The fillArray function takes a pointer arr and an integer size.
- It fills the array with values from 1 to size using a loop.
Print Array Function:
- The printArray function takes a pointer arr and an integer size.
- It prints the elements of the array using a loop.
Deallocate Array Function:
- The deallocateArray function takes a double pointer arr.
- It deallocates the memory of the array using free and sets the pointer arr to NULL.
Main Function:
- The main function declares a pointer array and an integer size.
- It prompts the user to enter the size of the array and reads the input.
- It calls the allocateArray function to allocate memory for the array.
- It calls the fillArray function to fill the array with values.
- It calls the printArray function to print the elements of the array.
- It calls the deallocateArray function to deallocate the memory of the array.
- It checks if the memory was successfully deallocated and prints the result.

Let's walk through the process of dynamic memory allocation, filling, printing, and deallocation:

Allocate Memory:

    Before Allocation:
    array -> NULL

    After Allocation (size = 5):
    array -> [_, _, _, _, _]

Fill Array with Values:

    array -> [1, 2, 3, 4, 5]

Print Array Elements:

    Output: 1 2 3 4 5

Deallocate Memory:

    Before Deallocation:
    array -> [1, 2, 3, 4, 5]

    After Deallocation:
    array -> NULL

The program dynamically allocates memory for the array, fills it with values, prints its elements, and deallocates the memory using free. The double pointer is used to handle the array in the main function and is passed to the functions for allocation and deallocation. This ensures that the changes made to the pointer in the functions are reflected in the main function.

Dynamic Array of Strings:

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

 // Function to add a string to the dynamic array
 void addString(char ***arr, int *size, const char *str) {
     // Reallocate memory to accommodate the new string
     *arr = (char **)realloc(*arr, (*size + 1) * sizeof(char *));
     if (*arr == NULL) {
         printf("Memory allocation failed\n");
         exit(1);
     }

     // Allocate memory for the new string and copy it to the array
     (*arr)[*size] = (char *)malloc((strlen(str) + 1) * sizeof(char));
     if ((*arr)[*size] == NULL) {
         printf("Memory allocation failed\n");
         exit(1);
     }
     strcpy((*arr)[*size], str);

     // Increment the size
     (*size)++;
 }

 // Function to remove a string from the dynamic array
 void removeString(char ***arr, int *size, const char *str) {
     for (int i = 0; i < *size; i++) {
         if (strcmp((*arr)[i], str) == 0) {
             // Free the memory for the string to be removed
             free((*arr)[i]);

             // Shift the remaining strings
             for (int j = i; j < *size - 1; j++) {
                 (*arr)[j] = (*arr)[j + 1];
             }

             // Reallocate memory to shrink the array
             *arr = (char **)realloc(*arr, (*size - 1) * sizeof(char *));
             if (*arr == NULL && *size - 1 > 0) {
                 printf("Memory allocation failed\n");
                 exit(1);
             }

             // Decrement the size
             (*size)--;
             return;
         }
     }
     printf("String \"%s\" not found in the array\n", str);
 }

 // Function to search for a string in the dynamic array
 int searchString(char **arr, int size, const char *str) {
     for (int i = 0; i < size; i++) {
         if (strcmp(arr[i], str) == 0) {
             return i; // Return the index if the string is found
         }
     }
     return -1; // Return -1 if the string is not found
 }

 // Function to print the strings in the dynamic array
 void printStrings(char **arr, int size) {
     for (int i = 0; i < size; i++) {
         printf("%s\n", arr[i]);
     }
 }

 int main() {
     char **array = NULL;
     int size = 0;

     // Add strings to the dynamic array
     addString(&array, &size, "Hello");
     addString(&array, &size, "World");
     addString(&array, &size, "Dynamic");
     addString(&array, &size, "Array");
     addString(&array, &size, "of Strings");

     printf("Array after adding strings:\n");
     printStrings(array, size);

     // Search for a string
     const char *searchStr = "World";
     int index = searchString(array, size, searchStr);
     if (index != -1) {
         printf("String \"%s\" found at index %d\n", searchStr, index);
     } else {
         printf("String \"%s\" not found in the array\n", searchStr);
     }

     // Remove a string from the dynamic array
     removeString(&array, &size, "Dynamic");
     printf("Array after removing \"Dynamic\":\n");
     printStrings(array, size);

     // Free the remaining allocated memory
     for (int i = 0; i < size; i++) {
         free(array[i]);
     }
     free(array);

     return 0;
 }

Add String Function:
- The addString function takes a double pointer to the array of strings, a pointer to the size of the array, and the string to be added.
- It reallocates memory for the array to accommodate the new string.
- It allocates memory for the new string and copies it to the array.
- It increments the size of the array.
Remove String Function:
- The removeString function takes a double pointer to the array of strings, a pointer to the size of the array, and the string to be removed.
- It searches for the string in the array.
- If the string is found, it frees the memory for the string and shifts the remaining strings.
- It reallocates memory to shrink the array.
- It decrements the size of the array.
Search String Function:
- The searchString function takes a pointer to the array of strings, the size of the array, and the string to be searched.
- It searches for the string in the array and returns the index if found, otherwise returns -1.
Print Strings Function:
- The printStrings function takes a pointer to the array of strings and the size of the array.
- It prints each string in the array.
Main Function:
- The main function initializes a double pointer to the array of strings and the size of the array.
- It adds strings to the array using the addString function.
- It prints the array after adding strings.
- It searches for a string in the array using the searchString function and prints the result.
- It removes a string from the array using the removeString function and prints the array after removal.
- It frees the remaining allocated memory for the strings and the array.

Let's walk through the process of adding, searching, removing, and deallocating strings in the dynamic array:

Add Strings:

    Initial Array:
    NULL

    Add "Hello":
    array -> [Hello]

    Add "World":
    array -> [Hello, World]

    Add "Dynamic":
    array -> [Hello, World, Dynamic]

    Add "Array":
    array -> [Hello, World, Dynamic, Array]

    Add "of Strings":
    array -> [Hello, World, Dynamic, Array, of Strings]

Search for a String:

    Search for "World":
    Found at index 1

Remove a String:

    Remove "Dynamic":
    Before removal:
    array -> [Hello, World, Dynamic, Array, of Strings]

    After removal:
    array -> [Hello, World, Array, of Strings]

Deallocate Memory:

    Free the remaining allocated memory:
    array -> NULL

The program dynamically allocates and deallocates memory for the array of strings, handles adding and removing strings, and searches for strings within the array. The use of double pointers ensures that changes made to the array in the functions are reflected in the main function.

DSA: Problems on Recursion, Pointers, and Dynamic Allocation

Comments

More from this blog

Computer Arithmetic: From Fast Adders to Floating-Point

The Complete Memory Hierarchy: From Semiconductor RAM to Virtual Memory

The Ultimate Spring Boot Guide: From Fundamentals to Production-Ready REST APIs

Understanding Functions, Memory, and Pointers in C: A Complete Guide

Datapath and Control

Hints

Solutions and Explanation:

Command Palette

Comments

More from this blog

Hints

Solutions and Explanation: