Recursion
1. Print 1-N, N-1, backtrack and print
static void OneToN(int n,int N){
if(n>N)return;
[Link](n);
OneToN(n+1,N);
}
static void OneToN_back(int n,int N){
if(n==0)return;
OneToN_back(n-1,N);
[Link](n);
}
2. Sum of first N (functional, parameterised)
Non parametrised :-
static int sum(int n){
if(n<=0){
return 0;
}
return n +sum(n-1);
}
3. Nth Fibonacci number
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
4. Reverse an array
void reverse(int[] arr, int i) {
int n = [Link];
if (i >= n / 2) return;
int temp = arr[i];
arr[i] = arr[n - i - 1];
arr[n - i - 1] = temp;
reverse(arr, i + 1);
}
5. Check palindrome string
boolean isPalindrome(String s, int i) {
int n = [Link]();
if (i >= n / 2) return true;
if ([Link](i) != [Link](n - i - 1)) return false;
return isPalindrome(s, i + 1);
}
6. What is a subsequence
A subsequence is a sequence that can be derived from another sequence
by deleting some or no elements without changing the order of the
remaining elements.
eg take a string: "abcde"
Some subsequences of this string include:
"abc" (delete d and e)
"ace" (delete b and d)
"a" (delete everything else)
"abcde" (the whole string itself)
"" (the empty subsequence)
The number of subsequences of a string of length n is:
2N
Each character has two choices:
Include it in the subsequence
Exclude it from the subsequenc
7. Print all the subsequences in an array.(recursion approach and power set
approach)
static void PrintSub(int index,ArrayList<Integer> seq,int[] arr,int n){
if(index==n){
[Link](seq);
return;
}
[Link](arr[index]);
PrintSub(index+1,seq,arr,n);
[Link]([Link]()-1);
PrintSub(index+1,seq,arr,n);
}
Time Complexity
At each index, we have 2 choices (include/exclude), so:
Total recursive calls = 2ⁿ
Each call may do some operations like add(), remove(), or print(), all of
which are O(1) amortized.
🧠 Space Complexity
1. Auxiliary/Recursive Stack Space
Max depth of recursion = n
So: O(n)
2. Space for seq
At most n elements in seq at a time
But since it's reused (not duplicated), we don’t count it multiple
times
8. Printing all subsequences whose sum is K.
static void printSum(int index,ArrayList<Integer> seq,int sum,int givenSum,int []arr,int n){
if(index==n){
if(sum==givenSum){
[Link](seq);
}
return;
}
[Link](arr[index]);
sum+=arr[index];
printSum(index+1,seq,sum,givenSum,arr,n);
sum-=arr[index];
[Link]([Link]()-1);
printSum(index+1,seq,sum,givenSum,arr,n);
}
9. Printing only 1 subsequences(stop when found 1) whose sum is K.
(without using flags)
static boolean printSumOnce(int index,ArrayList<Integer> seq,int sum,int
givenSum,int []arr,int n){
if(index==n){
if(sum==givenSum){
[Link](seq);
return true;
}
return false ;
}
[Link](arr[index]);
sum+=arr[index];
if(printSumOnce(index+1,seq,sum,givenSum,arr,n)==true)return true;
sum-=arr[index];
[Link]([Link]()-1);
if(printSumOnce(index+1,seq,sum,givenSum,arr,n)==true)return true;
return false;
}
Exaplantaion:-
The printSumOnce function is a recursive backtracking approach used to
find and print only the first subsequence of an array whose elements sum
up to a given target (givenSum). It explores each element by either
including or excluding it in the current subsequence (seq). The function
uses a boolean return type to short-circuit and stop recursion once a valid
subsequence is found. If a valid subsequence is reached at the base case
(index == n), it is printed and true is returned to prevent further
exploration. This approach ensures early termination and avoids checking
all 2ⁿ possibilities when only one valid result is needed.
10. Count Number of subsequences whose sum in K
pseudo code
F(){
Base case
Sum matches return 1
Dum doesn’t match return 0
Else
L= call Picking up
R= call not picking up
Return l+r
}
Code:-
static int printSumCount(int index,ArrayList<Integer> seq,int sum,int
givenSum,int []arr,int n){
if(index==n){
if(sum==givenSum){
return 1;
}
return 0;
}
[Link](arr[index]);
sum+=arr[index];
int l =printSumCount(index+1,seq,sum,givenSum,arr,n);
sum-=arr[index];
[Link]([Link]()-1);
int r =printSumCount(index+1,seq,sum,givenSum,arr,n);
return l+r;
}
11. Any optimisation you can do to improve above seq answers time
complexity ?
Yes , we can check if sum > give Sum and return from there itself but this
wont work in negative numbers case
COMBINATION SUM
12. Given an array on integers ..provide all possible combinations of these
summing upto a target …..its allowed to repeat integers
Code:-
static void find(int index, int target, ArrayList<Integer> seq, List<List<Integer>> ans,
int[] arr, int n) {
if (index == n) {
if (target == 0) { [Link](new ArrayList<>(seq));}
return;
}
// Take the element if it's not greater than target
if (arr[index] <= target) {
[Link](arr[index]);
find(index, target - arr[index], seq, ans, arr, n); // same index -> unlimited uses
[Link]([Link]() - 1); // backtrack
}
// Don't take the element, move to next index
find(index + 1, target, seq, ans, arr, n);
}
Simple Summary of the Approach:
You are finding all combinations from an array that add up to a target number. You
can pick the same number more than once.
At each step:
You can take the current number (and stay at the same index to reuse it).
Or you can skip it and move to the next number.
If the target becomes 0, you found a valid combination and add it to the result list.
We use backtracking (remove the last number after trying) to explore all possible
combinations.
O((2^T )* k): Total Recursive Calls * copying Task if average length is k
You are allowed to pick the same element multiple times.
At every index, you have two choices:
o Pick the element again (stay at the same index)
o Skip it (move to the next index)
So this builds a decision tree that can have up to 2^T recursive paths in the
worst case.
Why T? Because the smallest element might be 1, and we could go down the
tree T times to reach the target sum.
Space Complexity: O(T + A × K)
O(T) for recursion stack depth (in worst case, we go down to sum = 0).
O(A × K) for storing A combinations each of average size K. ‘,,
13. Given an array pick combinations such that sum == target and no
candidate can repeat (112 is allowed is array has two 1s)
static void findComb(int index,int target,List<Integer>
seq ,List<List<Integer>> ans,int []arr,int n){
if(target==0){
[Link](new ArrayList<>(seq));
return;
}
for(int i =index;i<n;i++){
if(i>index && arr[i]==arr[i-1]) continue;
if(arr[i]>target) break;
[Link](arr[i]);
findComb(i+1,target-arr[i],seq,ans,arr,n);
[Link]([Link]()-1);
}
}
Key Steps:
1. Sort the Array
This helps easily skip duplicates and allows early stopping if an element
exceeds the target.
2. Backtracking Function (findComb)
o If target == 0, the current combination (seq) is valid and is added
to the result.
o Loop through elements starting from the current index.
o Skip duplicates at the same recursive level using if (i > index &&
arr[i] == arr[i-1]).
o If current element > target, break the loop (since array is sorted).
o Else, include the element, recurse, and then backtrack by
removing the element.
14. Subset Sums in increasing order(powerset approach can be done too)
static void SubsetSum(int index,int
sum,List<Integer>comb,List<Integer> sums ,int[]arr,int n){
if(index==n){
[Link](sum);
return;
}
[Link](arr[index]);
SubsetSum(index+1,sum+arr[index],comb,sums,arr,n);
[Link]([Link]()-1);
SubsetSum(index+1,sum,comb,sums,arr,n);
}
15. Asf
16. Saf
17. Asf
18. Sfa
19. Sf
20. Af
21. Fas
22. F
23. sf