Scribd
Upload
3 views2 pages

Recursion Array Practice Sheet

The document outlines four recursion-based problems involving arrays: finding all paths in a maze, counting ways to reach the end of an array, solving the subset sum problem, and generating permutations of an integer array. Each problem includes a brief description, approach, and dry run examples to illustrate the solution. The focus is on using recursive techniques to solve these common algorithmic challenges.

Uploaded by

sakthi mahendran
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

Recursion Array Practice Sheet

The document outlines four recursion-based problems involving arrays: finding all paths in a maze, counting ways to reach the end of an array, solving the subset sum problem, and generating permutations of an integer array. Each problem includes a brief description, approach, and dry run examples to illustrate the solution. The focus is on using recursive techniques to solve these common algorithmic challenges.

Uploaded by

sakthi mahendran
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Recursion Practice Sheet - Array Based Problems

1. Find All Paths in a Maze (Right + Down Only)

Problem:
Given an N x N maze, print all paths from top-left to bottom-right by moving only right or down.

Approach:
- Start at (0,0), recursively move either right or down.
- Base condition: If you reach (N-1, N-1), print the path.

Dry Run for N=2:


Path: "DR" (Down then Right)
Path: "RD" (Right then Down)

Example Output for N=3:


DDR, DRD, DRR, RDR, RRD, RDD

2. Count Ways to Reach End of Array

Problem:
From index 0, move 1 or 2 steps at a time to reach end (index N).

Approach:
- At position i, call function recursively for i+1 and i+2.
- Stop if index goes beyond N.

Dry Run for N=4:


Ways from 0 to 4:
0->1->2->3->4
0->1->3->4
0->2->3->4
0->2->4
0->1->2->4
Total: 5 ways

3. Subset Sum Problem

Problem:
Check if there exists a subset whose sum equals a target value.

Approach:
- For each element, recursively include or exclude it.
- Base case: if sum == 0 -> return true; if no elements left -> return false.

Dry Run for arr={1,2,3}, target=5:


Try 3+2 -> Valid subset. So return true.

4. Permutations of Integer Array

Problem:
Recursion Practice Sheet - Array Based Problems

Print all permutations of an integer array.

Approach:
- Swap each element with itself and others in recursive manner.
- Backtrack by swapping back.

Dry Run for arr=[1,2,3]:


Level 1: 1 swapped with 1,2,3
Level 2: Fix next element and continue
Output: 6 permutations total

You might also like