Combination Sum II: Backtracking with Duplicate Handling

Day - 63 Combination Sum III The problem - Find all combinations of k numbers that sum to n, using only numbers 1-9, each number used at most once. Example : k = 3, n = 7 → [[1,2,4]] Brute Force - Generate all C(9, k) combinations, check each sum, still needs to enumerate all combinations. Approach Used - •) Initialize: Call findCombination(k, 1, n, new ArrayList<>(), ans) (start with number 1). •) findCombination(k, num, target, lst, ans), •) If (target == 0 && k == 0), found valid combination, add new ArrayList(lst) to ans and return. •) Recursive case, for num to 9, 1 - If i > target || k <= 0, break. 2 - Add i to lst. 3 - Recurse with k - 1 (need one less number), i + 1 (next number to try), target - i (remaining sum). 4 - Backtrack: remove i from lst. Complexity - Time - O(C(9, k) × k), C(9,k) combinations, k time to copy each. Space - O(k), recursion depth. Note - Loop from 1-9, add number, recurse with k-1 and target-num. Backtrack when target == 0 && k == 0! #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🔥 Day 97/100 of Code – Subsets II: Backtracking with Duplicate Pruning! Today solved a power set problem with duplicate elements — a clean extension of the classic subsets problem: ✅ Problem 90: Subsets II Task: Generate all unique subsets from an array that may contain duplicates. Approach: Sort + backtracking with level-skip logic: Sort array to group duplicates At each recursion level, iterate from ind to end: Skip duplicates: if (i != ind && nums[i] == nums[i-1]) continue Include nums[i], recurse with i+1 Backtrack Key Insight: The condition i != ind ensures we only take the first occurrence of a duplicate at each recursion depth, preventing duplicate subsets across different branches. Complexity: O(2^n) time worst-case, but pruning avoids duplicate subset generation. A subtle but crucial tweak to standard subset backtracking — handles real-world duplicate data elegantly! 🔄📦 #100DaysOfCode #LeetCode #Java #Backtracking #Subsets #DFS #Algorithm

Contains Duplicate — LeetCode 217 Hi all 👋 Today this is my first post related to a DSA problem. Goal Check whether an array contains duplicate numbers or not. n = Length of array idx = Index of array element Brute Force Approach Select each element and compare it with all other elements in the array. If any same value is found, return "true"; otherwise return "false". Time Complexity: O(n²) Space Complexity: O(1) Reason: every element is compared with others. Better Approach (Sorting) If we sort the array, duplicate elements come next to each other. After sorting, we simply compare adjacent elements. 🕸 Trap Empty array or single element array (idx < n-1) Time Complexity: O(n log n) Space Complexity: Depends on the sorting algorithm. Optimized Approach (Using Set) Before moving forward, let’s recall one important data structure — Set. A set: - Performs operations in average O(1) time - Does not allow duplicates Approach: - Traverse the array from the first element. - Check if the element already exists in the set. - If yes → duplicate found → return "true". - Otherwise, add the element to the set. The key idea: if we encounter the same element again, it means a duplicate exists. Time Complexity: O(n) Space Complexity: O(n) (in worst case when no duplicates exist) 🔁 Trade-off In real-world problems, we often optimize for time complexity. - If extra space is allowed → use Set (best time). - If space is restricted → prefer Sorting. Whenever you see duplicate or frequency type problems, think about: ➡️ Sorting ➡️ HashSet / HashMap If I missed anything or if you have a better approach, please feel free to add it in the comments. Thanks for reading 🙌 #DSA #LeetCode #Java #CodingJourney #DataStructures #Algorithms #ProblemSolving #SoftwareEngineer #TechLearning #InterviewPreparation

𝗠𝗼𝘀𝘁 𝗗𝗦𝗔 𝗽𝗿𝗼𝗯𝗹𝗲𝗺𝘀 𝗱𝗼𝗻’𝘁 𝗻𝗲𝗲𝗱 𝘀𝗺𝗮𝗿𝘁𝗲𝗿 𝗰𝗼𝗱𝗲. 𝗧𝗵𝗲𝘆 𝗻𝗲𝗲𝗱 𝗹𝗲𝘀𝘀 𝗿𝗲𝗽𝗲𝗮𝘁𝗲𝗱 𝘄𝗼𝗿𝗸. 𝗗𝗮𝘆 𝟯/𝟯𝟬 – DSA Pattern: Prefix Sum 🧠 How to spot this pattern If the problem has: • Multiple range sum queries • Subarray sum questions • “Sum from index L to R” • Brute force recalculates sums again and again 👉 Think Prefix Sum 💡 Simple idea Instead of adding numbers every time: Precompute sums once Store sum till each index Reuse it whenever needed Do the work once, use it many times. ✏️ Pseudocode 𝙥𝙧𝙚𝙛𝙞𝙭[0] = 𝙖𝙧𝙧[0] 𝙛𝙤𝙧 𝙞 𝙛𝙧𝙤𝙢 1 𝙩𝙤 𝙣-1:   𝙥𝙧𝙚𝙛𝙞𝙭[𝙞] = 𝙥𝙧𝙚𝙛𝙞𝙭[𝙞-1] + 𝙖𝙧𝙧[𝙞] 𝙨𝙪𝙢(𝙡, 𝙧):   𝙞𝙛 𝙡 == 0:     𝙧𝙚𝙩𝙪𝙧𝙣 𝙥𝙧𝙚𝙛𝙞𝙭[𝙧]   𝙧𝙚𝙩𝙪𝙧𝙣 𝙥𝙧𝙚𝙛𝙞𝙭[𝙧] - 𝙥𝙧𝙚𝙛𝙞𝙭[𝙡-1] LeetCode example : https://lnkd.in/gwGqPN8W 🧩 Problems that use this • Range sum queries • Subarray sum equals K • Equilibrium index • Difference array problems 🔥 One rule to remember If you’re adding the same elements again and again, you’re missing Prefix Sum. Once you build the prefix array, 👉 each query becomes O(1). Tomorrow: Hashing / Frequency Map 👍 if this helped Comment “DSA” to follow the 30-day pattern series. #DSA #ProblemSolving #Java #CodingInterviews #LearningInPublic #30DaysOfDSA

🚀 Day 47 Out of #365DaysOfCode - LeetCode Github link: https://lnkd.in/gGUy_MKZ Today I have worked on a classic problem: converting an integer into its corresponding Excel column title. At first glance, it looks like a simple base-26 conversion. But the interesting twist is that Excel columns are 1-based indexed and do not contain a zero character. That means we need to adjust the number before applying the modulus operation to correctly map values to letters. 💡 Key Learnings: Handling custom base conversions Managing edge cases with non-zero indexing Efficient string building using StringBuilder Strengthening problem-solving fundamentals ⏱️ Time Complexity: O(log₍26₎ n) #Java #DataStructures #Algorithms #ProblemSolving #CodingPractice

🔥 Day 304 – Daily DSA Challenge! 🔥 Problem: 🎯 Combination Sum II Given an array of candidate numbers (with possible duplicates) and a target value, return all unique combinations where the chosen numbers sum to the target. 👉 Each number can be used at most once in a combination. 💡 Key Insights: 🔹 This is a classic backtracking + pruning problem. 🔹 Sorting the array is crucial to handle duplicates efficiently. 🔹 Skip repeated elements at the same recursion level to avoid duplicate combinations. 🔹 Once a number exceeds the remaining target, we can stop early (thanks to sorting). 🔹 Always move to i + 1 since each element can be used only once. ⚡ Optimized Plan: ✅ Sort the candidates array ✅ Use backtracking to explore all valid combinations ✅ Maintain a temporary list (cur) for the current path ✅ Add the path to result when target == 0 ✅ Skip duplicates using if (i > idx && a[i] == a[i - 1]) ✅ Backtrack after each recursive call ✅ Time Complexity: O(2ⁿ) in the worst case ✅ Space Complexity: O(n) (recursion stack + current combination) 💬 Challenge for you: 1️⃣ What happens if we remove sorting — how do duplicates affect the output? 2️⃣ How is this problem different from Combination Sum I? 3️⃣ Can you convert this recursive solution into an iterative one? #DSA #LeetCode #Backtracking #Recursion #ProblemSolving #Java #KeepCoding

🔥 Day 98/100 of Code – Permutations: In-Place Backtracking with Swapping! Today revisited the classic permutation problem using an elegant in-place swapping approach: ✅ Problem 46: Permutations Task: Generate all permutations of distinct integers. Approach: Recursive swapping with index tracking: Fix elements step-by-step by swapping them into position At level i, swap nums[i] with each nums[j] where j ≥ i Recurse to i+1, then backtrack by swapping back Base case: when i == nums.length, store current array state Key Insight: By swapping in-place, we avoid extra space for temporary lists and naturally generate permutations without duplicate checks (since elements are distinct). Complexity: O(n × n!) time, O(n) recursion depth — optimal for generating all permutations. A clean, memory-efficient backtracking technique — fundamental for combinatorial generation! 🔄🧩 #100DaysOfCode #LeetCode #Java #Backtracking #Permutations #DFS #Algorithm

🔥 Day 309 – Daily DSA Challenge! 🔥 Problem: 🔁 Permutations II Given an array nums that may contain duplicate numbers, return all unique permutations in any order. 💡 Key Insights: 🔹 This is a backtracking problem with an extra twist — duplicates. 🔹 Sorting the array upfront is the key to handling duplicates cleanly. 🔹 Use a used[] boolean array to track which elements are already in the current permutation. 🔹 The golden rule to skip duplicates 👇     👉 If the current number is the same as the previous one and the previous one is not used, skip it. 🔹 This ensures we only generate unique permutations. ⚡ Optimized Plan: ✅ Sort the input array ✅ Use backtracking to build permutations ✅ Track used elements with a boolean array ✅ Add permutation to result when its size equals nums.length ✅ Skip duplicates using:     if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; ✅ Backtrack after each recursive call ✅ Time Complexity: O(n! × n) (due to copying permutations) ✅ Space Complexity: O(n) (recursion stack + used array) 💬 Challenge for you: 1️⃣ Why does the condition !used[i - 1] matter for avoiding duplicates? 2️⃣ How would this solution change if all numbers were unique? 3️⃣ Can you generate permutations iteratively instead of using recursion? #DSA #Day309 #LeetCode #Permutations #Backtracking #Recursion #Java #ProblemSolving #KeepCoding #100DaysOfCode

🚀 Day 16 - 100Days of DSA Problem Statement : ✅ Sum of subarrays of size K ✅ Average of subarrays of size K At first, calculating the sum or average of every subarray looked simple… but using nested loops makes it slow and inefficient for large inputs. That’s when I learned about the Sliding Window technique – a powerful optimization used in many real-world and interview problems. 🧠 Approach: Sliding Window Technique 1️⃣ Create a window of size k 2️⃣ Calculate the sum of the first window 3️⃣ Slide the window one step at a time 4️⃣ Subtract the element going out 5️⃣ Add the element coming in Code template to solve similar problems: int maxSum=0,windowSum=0; List<Integer> list = new ArrayList<>(); for(int right=0;right<size;right++) { maxSum = maxSum+arr[right]; } list.add(maxSum); for(int right=size;right<arr.length;right++) { maxSum+=arr[right]; maxSum-=arr[right-size]; list.add(maxSum); } ⏱ Time & Space Complexity Time Complexity: 🟢 O(n) – each element is processed once Space Complexity: 🟢 O(1) – only a few variables used (constant extra space) #Day16 #SlidingWindow #DSA #Java #ProblemSolving #CodingJourney #JavaDeveloper #BackendDevelopment #Algorithms #Consistency

🚀 Daily DSA Practice – Day 41 | Binary Search Tree (BST) Fundamentals (Java) Continuing my Data Structures & Algorithms preparation, today I focused on Binary Search Tree (BST) fundamentals, understanding how ordered tree properties help achieve efficient searching and validation operations. 📌 Problems Solved (LeetCode): • 700. Search in a Binary Search Tree – Leveraged BST ordering to achieve efficient lookup • 98. Validate Binary Search Tree – Used min/max boundary recursion to ensure correctness • 235. Lowest Common Ancestor of a BST – Applied BST properties to optimize ancestor search 🎯 Key Learnings: ✔ How BST ordering reduces time complexity for search operations ✔ Using range constraints (min/max) for accurate validation ✔ Difference between general Binary Tree vs BST logic ✔ Writing cleaner and faster recursive solutions using properties instead of brute force BST problems are highly relevant in technical interviews because they test optimization thinking, recursion clarity, and understanding of ordered data structures, which are crucial for backend systems and database indexing concepts. #DSA #LeetCode #Java #BinarySearchTree #BST #Recursion #TreeAlgorithms #ProblemSolving #InterviewPreparation #BackendDeveloper #SoftwareEngineer