Scribd
Upload
9 views2 pages

Advanced Recursion: Fibonacci & Subsets

The document discusses two classic recursion problems: climbing stairs and generating unique subsets. For the climbing stairs problem, the number of ways to reach step n is defined recursively as ways(n) = ways(n-1) + ways(n-2), with base cases for n = 0 and n < 0. The unique subsets problem involves using backtracking to explore all combinations of elements in an array, with a helper function to manage the inclusion and exclusion of elements.

Uploaded by

Monali Borade
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
9 views2 pages

Advanced Recursion: Fibonacci & Subsets

The document discusses two classic recursion problems: climbing stairs and generating unique subsets. For the climbing stairs problem, the number of ways to reach step n is defined recursively as ways(n) = ways(n-1) + ways(n-2), with base cases for n = 0 and n < 0. The unique subsets problem involves using backtracking to explore all combinations of elements in an array, with a helper function to manage the inclusion and exclusion of elements.

Uploaded by

Monali Borade
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

Advanced Recursion

Fibonacci Series and Climbing Stairs

This problem is a classic example of recursion, which you can often solve with a
Fibonacci-like approach. The goal is to find the total number of distinct ways to climb to the
top of a staircase with n steps, where you can take either one or two steps at a time.

The key insight is that the number of ways to reach step n is the sum of the ways to reach
step n-1 (by taking a single step) and the ways to reach step n-2 (by taking a double step).
This gives us the recursive formula: ways(n) = ways(n-1) + ways(n-2).

The base cases are crucial for stopping the recursion:

●​ n = 0: There's one way to be at the top of a 0-step staircase (by doing nothing).
●​ n < 0: There are no ways to climb a negative number of steps.

Here is the Java code for this solution:

Java
class Solution {
public int climbStairs(int n) {
if (n == 0) {
return 1;
}
if (n < 0) {
return 0;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
}

Printing Unique Subsets

Generating all unique subsets of a given array is another common recursion problem, often
solved using backtracking. The core idea is to explore every possible path to build a
subset. At each element in the array, you have two choices:

1.​ Include the current element in your subset.


2.​ Exclude the current element from your subset.
You make a recursive call for each choice and then "backtrack" to explore the other option.
The base case is when you've considered every element in the array; at that point, you've
formed a complete subset and can add it to your list of results.

Here is the provided Java code, which uses a helper function f to implement this logic:

Java
class Solution {
private void f(int i, List<Integer> arr, int[] nums, List<List<Integer>> ans) {
if (i == [Link]) {
[Link](new ArrayList<>(arr));
return;
}

// Include the current element


[Link](nums[i]);
f(i + 1, arr, nums, ans);

// Exclude the current element (backtrack)


[Link]([Link]() - 1);
f(i + 1, arr, nums, ans);
}

public List<List<Integer>> subsets(int[] nums) {


List<List<Integer>> ans = new ArrayList<>();
List<Integer> arr = new ArrayList<>();
f(0, arr, nums, ans);
return ans;
}
}

You might also like