🔁 Recursion & Backtracking – Java

This repository contains Java programs that solve classic subsequence and permutation problems using recursion and backtracking.

---

📁 Files Overview

🔹 Subsequence Problems

1. GenerateAllSubsequences.java
   ➤ Generate all possible subsequences of an array using recursion.

2. SubsequenceWithSumK.java
   ➤ Return all subsequences whose sum is equal to K.

3. OneSubsequenceWithSumK.java
   ➤ Return any one subsequence whose sum is equal to K.

4. CountSubsequenceWithSumK.java
   ➤ Count total number of subsequences whose sum is equal to K.

---

🔹 Sorting Algorithms (Bonus)

5. RandomizedQuickSort.java
   ➤ Sort an array using Hoare's partition and a random pivot (Quick Sort variant).

6. MergeSort.java
   ➤ Sort an array using the Merge Sort algorithm.

---

🔹 Combination & Subset Problems

7. CombinationSum.java
   ➤ Find all combinations where elements (can be reused multiple times) sum up to a target value.

8. CombinationSum-II.java
   ➤ Find all unique combinations where each element is used at most once and the sum equals the target.
   ➤ Handles duplicates gracefully to avoid duplicate combinations.

9. SubsetSums.java
   ➤ Return the sum of all subsets of a given array using recursion.

10. SubsetsWithDup.java
    ➤ Generate all unique subsets of an array that may contain duplicates using backtracking.

---

🔹 Permutation Problems

11. Permutations_Approach_I.java ✅
    ➤ Generate all possible permutations of an array using backtracking with a freq[] boolean array.
    ➤ Ensures that each element is used once per permutation.

12. Permutations_Approach_II.java ✅
    ➤ Generate permutations using in-place swapping, reducing space overhead.
    ➤ Fix one index at a time and recursively swap the remaining elements.

---

🙌 Author

Rahul Gupta
🎯 Building strong foundations in Recursion, Backtracking & DSA using Java.

---

📌 Coming Soon

• 🔜 N-Queens Problem
• 🔜 Palindrome Partitioning
• 🔜 Word Break (Backtracking + Memoization)