Unique Subsets with Duplicates

Day - 62 Generate Parentheses The problem - Given n pairs of parentheses, generate all combinations of well formed parentheses. Example : n = 3 → ["((()))","(()())","(())()","()(())","()()()"] Brute Force - Generate all 2^(2n) combinations, then filter for valid ones, still exponential. Approach Used - •) Initialize: Call DFS(0, 0, "", n, res) (start with 0 open, 0 close, empty string). •) DFS(openP, closeP, s, n, res), 1 - Base case, if openP == closeP == n: add s to res (valid combination) and return. 2 - Recursive First case, if openP < n: add '(', recurse with openP+1. 3 - Recursive Second case, if closeP < openP: add ')', recurse with closeP+1. Complexity - Time - O(4^n / √n), the number of valid combinations. Space - O(n), recursion depth. Note - Track open and close parentheses count. Add '(' if open < n, add ')' if close < open. Recurse until both equal n. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day 49 Problem statement: You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13. For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers. The test cases are generated so that the answer fits in a 32-bits integer Example: For the tree [1,0,1,0,1,0,1] Paths formed: 100 → 4 101 → 5 110 → 6 111 → 7 Total = 22 Approach: While traversing the tree using DFS, we build the binary number step by step. At each node: val = 2 * val + root.val Why multiply by 2? Because in binary: Left shift = multiply by 2 Then add current bit This simulates constructing a binary number as we move down the tree. Approach: Use DFS (Preorder traversal) Carry the current binary value When we reach a leaf → return the computed number Sum left and right subtree results Java code class Solution { public int dfs(TreeNode root, int val){ if(root == null) return 0; val = 2 * val + root.val; if(root.left == null && root.right == null){ return val; } return dfs(root.left, val) + dfs(root.right, val); } public int sumRootToLeaf(TreeNode root) { return dfs(root, 0); } } #HappyCoding #DSA #Trees #LeetCode #DSA #BinaryTree #Algorithms #Java #ProblemSolving #CodingJourney #InterviewPreparation #SoftwareEngineering #CareerGrowth

Day - 73 Valid Parentheses The problem - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if: open brackets are closed by the same type of brackets, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket. Brute Force - Repeatedly scan the string and remove valid pairs like "()", "{}", "[]" until no more pairs can be removed. If the string becomes empty, it's valid. This gives O(n²) time complexity due to multiple passes and string manipulation. Approach Used - •) Create a Stack<Character> to track opening brackets •) Create a HashMap<Character, Character> to map closing to opening brackets, ')' → '(' , '}' → '{' and ']' → ‘[‘. •) Process each character, Iterate through each character c in the string, 1 - If c is an opening bracket, push it onto the stack. 2 - If c is a closing bracket, - Check if stack is empty, return false. - ⁠Pop from stack and check if it matches mapping.get(c), if mismatch → return false. •) Final Validation, 1 - After processing all characters, check if stack is empty. 2 - Empty stack means all brackets matched correctly. 3 - Non-empty stack means unmatched opening brackets remain. Complexity - Time - O(n), single pass through the string, each character processed once and stack operations (push/pop) are O(1). Space - O(n), stack can hold up to n/2 opening brackets in worst case. Note - Stack naturally handles nested structures with LIFO (Last-In-First-Out) behavior. Each closing bracket must match the most recent unmatched opening bracket. HashMap enables O(1) lookup for matching pairs, making validation efficient. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 65 Letter Combinations of Phone Number The problem - Given string of digits 2-9, return all possible letter combinations that the number could represent (like old phone keypads). Example : digits = "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"] Brute Force - Generate all combinations iteratively using nested loops - works but becomes unwieldy with variable input length. Approach Used - •)Create map, 2→"abc", 3→"def", 4→"ghi", 5→"jkl", 6→"mno", 7→"pqrs", 8→"tuv", 9→"wxyz" •) Handle edge case, if digits is null or empty, return empty list. •) Initialize, call backtrack(digits, 0, new StringBuilder(), res, map). •) Backtrack(digits, idx, comb, res, map), 1 - Base Condition, if idx == digits.length, add comb to res. 2 - Recursive case, get letters for current digit, String letters = map.get(digits.charAt(idx)). 3 - For each letter, append to comb, recurse with idx+1, backtrack(digits, idx + 1, comb, res, map). Remove last character, comb.deleteCharAt(comb.length() - 1). Complexity - Time - O(4^n × n), max 4 letters per digit, n to build each string. Space - O(n), recursion depth. Note - Use map for digit→letters. For each digit, try all its letters, recurse to next digit. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

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

Contains Duplicate – LeetCode Solution 📌 Problem Statement Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. 🔗 Problem Link: https://lnkd.in/gY2dtJ9m ⸻ 💡 Approach To solve this problem efficiently, we use a HashSet. Why HashSet? • A HashSet does not allow duplicate elements. • It provides O(1) average time complexity for add() and contains() operations. Algorithm Steps: 1. Create an empty HashSet. 2. Traverse through each element in the array. 3. For every number: • If it already exists in the set → return true. • Otherwise, add it to the set. 4. If no duplicates are found after the loop → return false. ⸻ 🧠 Time & Space Complexity • Time Complexity: O(n) (We traverse the array once) • Space Complexity: O(n) (In worst case, all elements are stored in the HashSet) #java #dsa #javaprogram

🔥 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

After exploring path-based recursion, I moved to generating all subsets of a string. This introduced a very clean pattern - For every element, you either include it or exclude it. That’s it. But that “either-or” creates a full decision tree. What became clear here: - Every element creates two branches. - Total subsets = 2ⁿ (tree expansion becomes visible). - Recursion can systematically explore combinations. - The structure is more important than the syntax. Core logic : if (index == str.length()) {   System.out.println(current);   return; } subset(index + 1, current + str.charAt(index)); // include subset(index + 1, current);  // exclude This is where recursion started feeling predictable. Once the pattern is seen, similar problems start looking connected. #recursion #java #dsajourney #backtracking #problemSolving

𝗗𝗮𝘆 𝟮𝟬/𝟮𝟬 — 𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 𝗖𝗵𝗮𝗹𝗹𝗲𝗻𝗴𝗲 Solved 3Sum using Sorting + Two Pointer technique. ➤ Approach (O(n²), O(1) extra space apart from result): • First, sort the array • Fix one element i • Use two pointers (left, right) to find pairs such that --> nums[i] + nums[left] + nums[right] == 0 • Move pointers based on whether the sum is smaller or larger than zero • Store unique triplets ➤ Key Insight: Sorting simplifies the problem. Once sorted, the two-pointer technique efficiently avoids checking every combination. Brute force would be O(n³). Optimized approach reduces it to O(n²). #LeetCode #Java #DSA #TwoPointers #Sorting #ProblemSolving #20DaysChallenge #Consistency

🚀 DSA Tip: Two Pointer Approach for Target Sum If your array is sorted, you don’t need nested loops to find a pair with a given target sum. 👉 Use the Two Pointer Technique — simple and O(n)! 💡 How it works: • Place one pointer at the start (left) • Place another at the end (right) • Compare their sum with the target ✅ If sum is small → move left++ ✅ If sum is large → move right-- ✅ If equal → 🎯 pair found ⏱️ Complexity: Time → O(n) Space → O(1) 🔥 When to use: ✔️ Target sum in sorted array ✔️ Pair problems ✔️ Remove duplicates ✔️ Reverse problems Mastering two pointers can save you from unnecessary O(n²) solutions! #DSA #CodingInterview #Java #TwoPointers #ProblemSolving #TechLearning