Combination Sum with Backtracking and Recursion

#200DaysOfCode – Day 106 Backtracking & Recursion | Combination Sum II Problem: Combination Sum II Task: Given an array of candidate numbers and a target, find all unique combinations where the numbers sum up to the target. Each number can be used only once, and duplicate combinations are not allowed. Example: Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [1,1,6], [1,2,5], [1,7], [2,6] My Approach: Sorted the array to handle duplicates efficiently. Used backtracking to explore all valid combinations. Skipped duplicate elements to avoid repeated combinations. Pruned recursion when the current value exceeded the target. Time Complexity: Exponential (Backtracking) Space Complexity: O(N) due to recursion stack Backtracking becomes much cleaner and more efficient when combined with sorting and smart pruning. Understanding when to skip elements is just as important as choosing them. #takeUforward #100DaysOfCode #Java #ProblemSolving #LeetCode #Backtracking #Recursion #DSA #CodingJourney #CodeNewbie #Consistency

🧠 Day 76 of #100DaysOfLeetCode 📌 Problem: Combination Sum II 📊 Difficulty: Medium 💡 Key Insight: Sorting the array helps handle duplicates. While backtracking, duplicates are skipped only in the “not pick” path to ensure unique combinations. 🛠️ Approach: Sort the candidates array Use backtracking to explore combinations Each number can be used once → move to index + 1 Skip duplicate elements to avoid repeated combinations ⏱️ Complexity: Time: O(2^n) Space: O(n) #LeetCode #Java #ProblemSolving #CodingChallenge #100DaysOfCode #DSA #LearningEveryday

#200DaysOfCode – Day 107 Subsets with Duplicates Problem:- Subsets II (LeetCode 90) Task: Given an integer array nums that may contain duplicates, return all possible unique subsets (power set). Example: Input: nums = [1,2,2] Output: [[], [1], [1,2], [1,2,2], [2], [2,2]] My Approach: Sorted the array to bring duplicate elements together. Used Backtracking to generate all subsets. Skipped duplicate elements at the same recursion level to avoid repeating subsets. Complexity Analysis: Time Complexity: O(2^N) Space Complexity: O(N) (recursion stack, excluding output) Handling duplicates becomes much easier when the input is sorted and recursion levels are controlled carefully. Backtracking problems look complex at first but the logic becomes clean once broken into steps. #takeUforward #100DaysOfCode #Java #LeetCode #ProblemSolving #Backtracking #Recursion #DSA #CodingJourney #CleanCode #DeveloperLife

Day 7/100 – LeetCode Challenge 🚀 Problem: Remove Element Approach: Used two pointers Shifted non-matching elements to the front Returned the count of valid elements Time Complexity: O(n) Space Complexity: O(1) (in-place) Key takeaway: In-place array problems often reduce to index management, not extra data structures. #LeetCode #100DaysOfCode #DSA #Java #ProblemSolving #InterviewPrep #100DaysOfLeetCode

Day 8/100 – LeetCode Challenge 🚀 Problem: Implement strStr() Approach: Checked every possible starting index in haystack Matched characters one by one with needle Time Complexity: O(n × m) Space Complexity: O(1) Key takeaway: Brute-force solutions are fine when constraints allow them. Understanding the basic approach comes before optimization. #LeetCode #100DaysOfCode #DSA #Java #ProblemSolving #100DaysOfLeetCode

#day280 of #1001daysofcode problem statement (0085): Maximal Rectangle. For each row, I converted the matrix into a histogram of consecutive 1s and didn't change the Largest Rectangle in Histogram code which i uploaded earlier. Key takeaway: -> Break problems into familiar subproblems   -> Reusability of concepts matters more than memorizing solutions   -> In histogram-based solutions, resetting height on '0' is crucial   #DSA #Java #LeetCode #ProblemSolving Shivam Mahajan #leetcode #1001daysofcode

 Day 10/100 Q 12 – Remove Duplicates from Sorted Array (DSA) Today’s problem was all about in-place array manipulation and two-pointer technique. 📌 Problem Statement Given a sorted integer array, remove duplicates in-place so that each unique element appears only once and return the count of unique elements. 🧠 Key Insight Since the array is already sorted, duplicates appear next to each other. Using two pointers, we can overwrite duplicates and keep all unique elements at the beginning of the array without using extra space. ⚙️ Approach Use one pointer to track the last unique element Traverse the array with another pointer Update the array when a new unique element is found ⏱ Complexity Time: O(n) Space: O(1) 💡 What I Learned How sorting simplifies duplicate problems Practical use of the two-pointer technique Writing space-optimized solutions 🔁 On to the next challenge! Consistency > Motivation 💪 #100DaysOfDSA #DSA #Arrays #TwoPointers #Java #ProblemSolving #LeetCode #CodingJourney #DailyLearning

#PostLog115 𝐂𝐫𝐚𝐜𝐤𝐢𝐧𝐠 𝐑𝐞𝐩𝐞𝐚𝐭𝐞𝐝 𝐒𝐭𝐫𝐢𝐧𝐠 𝐌𝐚𝐭𝐜𝐡 (LeetCode #686) 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 𝐅𝐨𝐥𝐥𝐨𝐰𝐞𝐝: Instead of repeating string 𝐚 endlessly, the idea was to repeat it just enough so that string 𝐛 could possibly fit inside it. 1.Start with an empty string and keep appending 𝐚 until the length becomes at least the length of 𝐛. This ensures we have a fair window where 𝐛 might appear. 2.Check if 𝐛 is a substring at this stage. If yes, we already have the minimum number of repetitions. 3.If not, append 𝐚 one more time and check again. This extra repetition is crucial because 𝐛 can overlap between two consecutive repetitions of a 𝐚 4.If 𝐛 still doesn’t appear, we can safely conclude that it’s impossible. Why this works: A substring can only stretch across at most one boundary between repetitions. Going beyond one extra repetition adds no new possibilities, only extra cost. #PostLog115 #LeetCode #DSA #Java #StringAlgorithms #ProblemSolving

🔥 Day 82 of #100DaysOfLeetCode ✅ Problem: Number of Longest Increasing Subsequence ✅ Difficulty: Medium 💡 Key Insight: Instead of tracking only the LIS length, we also maintain the number of ways each LIS can be formed. For every element, we check all previous smaller elements and update both length and count dynamically. 🛠 Approach: Use two arrays: dp[i] → Length of LIS ending at index i cnt[i] → Number of LIS ending at index i If a longer subsequence is found → update length and copy count. If another subsequence of the same length is found → add the counts. Finally, sum counts for indices having the maximum LIS length. ⏱ Complexity: Time: O(n²) Space: O(n) #LeetCode #Java #ProblemSolving #CodingChallenge #100DaysOfCode #DSA #LearningEveryday

🔹 Day 98 – LeetCode Practice 📌 Problem: Path Sum II (LeetCode #113) 📊 Difficulty: Medium 🧠 Problem Overview: Given the root of a binary tree and a target sum, the task is to find all root-to-leaf paths where the sum of node values equals the target. Each valid path should be returned as a list of values. ✅ Approach Used: Traversed the tree using depth-first search. Maintained the current path and cumulative sum while moving down the tree. When a leaf node was reached, checked if the sum matched the target. Used backtracking to explore all possible paths correctly. 📈 Submission Results: Status: Accepted ✅ Runtime: 2 ms Memory Usage: 45.54 MB 💡 Reflection: This problem is a great example of how recursion and backtracking work together in tree problems. Managing state carefully is key to collecting all valid paths without duplication. #LeetCode #BinaryTree #DFS #Backtracking #Java #DSA #CodingPractice