Search Blogs

Showing results for "Combinatorics"

Found 3 results

Subsets Problem (LeetCode 78) Explained | Recursion, Iterative & Bit Manipulation

IntroductionThe Subsets problem (LeetCode 78) is one of the most fundamental and frequently asked questions in coding interviews. It introduces the concept of generating a power set, which is a core idea in recursion, backtracking, and combinatorics.Mastering this problem helps in solving a wide range of advanced problems like combinations, permutations, and decision-based recursion.In this article, we will explore:Intuition behind subsetsRecursive (backtracking) approachIterative (loop-based) approachBit manipulation approachTime and space complexity analysisProblem StatementGiven an integer array nums of unique elements, return all possible subsets (the power set).Key PointsEach element can either be included or excludedNo duplicate subsetsReturn subsets in any orderExamplesExample 1Input:nums = [1, 2, 3]Output:[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Example 2Input:nums = [0]Output:[[], [0]]Key InsightFor each element, there are two choices:Include it OR Exclude itSo total subsets:2^nThis makes it a binary decision tree problem, very similar to:Permutation with SpacesBinary choices recursionBacktracking problemsApproach 1: Recursion + Backtracking (Most Important)IntuitionAt each index:Skip the elementInclude the elementBuild subsets step by step and backtrack.Java Code (With Explanation)import java.util.*;class Solution { List<List<Integer>> liss = new ArrayList<>(); void solve(int[] an, int ind, List<Integer> lis) { // Base case: reached end → one subset formed if (ind == an.length) { liss.add(new ArrayList<>(lis)); // store copy return; } // Choice 1: Do NOT include current element solve(an, ind + 1, lis); // Choice 2: Include current element lis.add(an[ind]); solve(an, ind + 1, lis); // Backtrack: remove last added element lis.remove(lis.size() - 1); } public List<List<Integer>> subsets(int[] nums) { List<Integer> lis = new ArrayList<>(); solve(nums, 0, lis); return liss; }}Dry Run (nums = [1,2])Start: [] → skip 1 → [] → skip 2 → [] → take 2 → [2] → take 1 → [1] → skip 2 → [1] → take 2 → [1,2]Final Output:[], [2], [1], [1,2]Approach 2: Iterative (Loop-Based)IntuitionStart with an empty subset:[ [] ]For each element:Add it to all existing subsetsCodeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); for (int num : nums) { int size = result.size(); for (int i = 0; i < size; i++) { List<Integer> temp = new ArrayList<>(result.get(i)); temp.add(num); result.add(temp); } } return result; }}How It WorksFor [1,2,3]:Start: [[]]Add 1 → [[], [1]]Add 2 → [[], [1], [2], [1,2]]Add 3 → [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Approach 3: Bit ManipulationIntuitionEach subset can be represented using a binary number:For n = 3:000 → []001 → [1]010 → [2]011 → [1,2]...Codeimport java.util.*;class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); int n = nums.length; int total = 1 << n; // 2^n for (int i = 0; i < total; i++) { List<Integer> subset = new ArrayList<>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { subset.add(nums[j]); } } result.add(subset); } return result; }}Complexity AnalysisApproachTime ComplexitySpace ComplexityRecursionO(2^n)O(n) stackIterativeO(2^n)O(2^n)Bit ManipulationO(2^n)O(2^n)Why All Approaches Are O(2ⁿ)Because:Total subsets = 2ⁿEach subset takes up to O(n) to constructWhen to Use Which ApproachRecursion / Backtracking → Best for interviews (easy to explain)Iterative → Clean and beginner-friendlyBit Manipulation → Best for optimization & advanced understandingKey TakeawaysSubsets = power set problemEvery element → 2 choicesThink in terms of decision treesBacktracking = build + undo (add/remove)Common Interview VariationsSubsets with duplicatesCombination sumPermutationsK-sized subsetsConclusionThe Subsets problem is a foundational DSA concept that appears across many interview questions. Understanding all approaches—especially recursion and iterative expansion—gives a strong base for solving complex backtracking problems.If you master this pattern, you unlock a whole category of problems in recursion and combinatorics.Frequently Asked Questions (FAQs)1. Why are there 2ⁿ subsets?Because each element has 2 choices: include or exclude.2. Which approach is best for interviews?Recursion + backtracking is the most preferred.3. Is bit manipulation important?Yes, it helps in optimizing and understanding binary patterns.

LeetCodeMediumJavaRecursionBacktracking

All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

IntroductionThe Power Set problem for strings is a classic question in recursion and backtracking, frequently asked in coding interviews and platforms like GeeksforGeeks.In this problem, instead of numbers, we deal with strings and generate all possible subsequences (not substrings). This makes it slightly more interesting and practical for real-world applications like pattern matching, text processing, and combinatorics.In this article, we will cover:Intuition behind subsequencesRecursive (backtracking) approachSorting for lexicographical orderAlternative approachesComplexity analysisProblem StatementGiven a string s of length n, generate all non-empty subsequences of the string.RequirementsReturn only non-empty subsequencesOutput must be in lexicographically sorted orderExamplesExample 1Input:s = "abc"Output:a ab abc ac b bc cExample 2Input:s = "aa"Output:a a aaSubsequence vs Substring (Important)Substring: Continuous charactersSubsequence: Characters can be skippedExample for "abc":Subsequences → a, b, c, ab, ac, bc, abcKey InsightFor every character, we have two choices:Include it OR Exclude itSo total subsequences:2^nWe generate all and then remove the empty string.Approach 1: Recursion (Backtracking)IntuitionAt each index:Skip the characterInclude the characterBuild all combinations recursivelyJava Code (With Explanation)import java.util.*;class Solution { // List to store all subsequences List<String> a = new ArrayList<>(); void sub(String s, int ind, String curr) { // Base case: reached end of string if (ind == s.length()) { a.add(curr); // add current subsequence return; } // Choice 1: Exclude current character sub(s, ind + 1, curr); // Choice 2: Include current character sub(s, ind + 1, curr + s.charAt(ind)); } public List<String> AllPossibleStrings(String s) { // Start recursion sub(s, 0, ""); // Remove empty string (not allowed) a.remove(""); // Sort lexicographically Collections.sort(a); return a; }}Step-by-Step Dry Run (s = "abc")Start: ""→ Exclude 'a' → "" → Exclude 'b' → "" → Exclude 'c' → "" → Include 'c' → "c" → Include 'b' → "b" → Exclude 'c' → "b" → Include 'c' → "bc"→ Include 'a' → "a" → Exclude 'b' → "a" → Exclude 'c' → "a" → Include 'c' → "ac" → Include 'b' → "ab" → Exclude 'c' → "ab" → Include 'c' → "abc"Final Output (After Sorting)a ab abc ac b bc cApproach 2: Bit ManipulationIntuitionEach subsequence can be represented using binary numbers:0 → exclude1 → includeCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); int n = s.length(); int total = 1 << n; // 2^n for (int i = 1; i < total; i++) { // start from 1 to avoid empty StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { sb.append(s.charAt(j)); } } result.add(sb.toString()); } Collections.sort(result); return result; }}Approach 3: Iterative (Expanding List)IdeaStart with empty listFor each character:Add it to all existing subsequencesCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); result.add(""); for (char ch : s.toCharArray()) { int size = result.size(); for (int i = 0; i < size; i++) { result.add(result.get(i) + ch); } } result.remove(""); Collections.sort(result); return result; }}Complexity AnalysisTime Complexity: O(n × 2ⁿ)Space Complexity: O(n × 2ⁿ)Why?Total subsequences = 2ⁿEach subsequence takes O(n) to buildWhy Sorting is RequiredThe recursion generates subsequences in random order, so we sort them:Collections.sort(result);This ensures lexicographical order as required.Key TakeawaysThis is a power set problem for stringsEach character → 2 choicesRecursion = most intuitive approachBit manipulation = most optimized thinkingAlways remove empty string if requiredCommon Interview VariationsSubsets of arrayPermutations of stringCombination sumSubsequence with conditionsConclusionThe Power Set problem is a fundamental building block in recursion and combinatorics. Once you understand the include/exclude pattern, you can solve a wide range of problems efficiently.Mastering this will significantly improve your ability to tackle backtracking and decision tree problems.Frequently Asked Questions (FAQs)1. Why is the empty string removed?Because the problem requires only non-empty subsequences.2. Why is time complexity O(n × 2ⁿ)?Because there are 2ⁿ subsequences and each takes O(n) time to construct.3. Which approach is best?Recursion → best for understandingBit manipulation → best for optimization

GeeksforGeeksRecursionJavaBacktrackingMedium

LeetCode 1569: Number of Ways to Reorder Array to Get Same BST – Java Solution & Explanation

IntroductionImagine inserting a sequence of numbers into a Binary Search Tree (BST). The first number becomes the root, smaller values move to the left subtree, and larger values move to the right subtree.Now consider an interesting question: Can the numbers be rearranged into a different order while producing exactly the same BST?The answer is yes.For example, the arrays [2, 1, 3] and [2, 3, 1] produce the same BST. The root remains 2, while 1 belongs to the left subtree and 3 belongs to the right subtree. The insertion order between those two subtrees can change without changing the final tree.This is the central idea behind LeetCode 1569 – Number of Ways to Reorder Array to Get Same BST.The challenge is that the number of possible reorderings can grow rapidly. Generating every permutation would be far too expensive. Instead, we can count valid arrangements mathematically using combinations, then combine those counts recursively for the left and right subtrees.There is one more problem: calculating combinations repeatedly using factorials can lead to unnecessary work and large intermediate numbers. Pascal’s Triangle provides a convenient way to precompute the required combination values.Let's build the solution from the beginning.Problem StatementProblem Link - Number of Ways to Reorder Array to Get Same BSTGiven an array nums containing a permutation of the integers from 1 to n, insert its elements in order into an initially empty BST.Return the number of different reorderings of nums that produce exactly the same BST as the original array.The original ordering itself is included in the total, but the answer must count only the other reorderings, so the original arrangement must be subtracted once.Since the answer may be large, return it modulo:1,000,000,007Example 1Input: nums = [2, 1, 3]Output: 1The original array creates this BST:2/ \1 3The array [2, 3, 1] creates the same tree.There are two valid arrangements in total, including the original one. After excluding the original ordering, the answer is 1.Example 2Input: nums = [3, 4, 5, 1, 2]Output: 5There are six valid arrangements in total, including the original sequence. Subtracting the original arrangement gives 5.Example 3Input: nums = [1, 2, 3]Output: 0The BST is a right-skewed tree. Every value must appear in increasing order to produce that same tree, so no alternative ordering exists.Step 1: The First Element Always Becomes the RootThe first observation comes directly from how a BST is constructed.Consider:nums = [3, 1, 2, 4, 5]The first element, 3, becomes the root.Every remaining value is divided into two groups:Values smaller than 3 go to the left subtree.Values greater than 3 go to the right subtree.The groups are:Left: [1, 2]Right: [4, 5]The resulting BST is:3/ \1 4\ \2 5The root must remain 3 in every valid reordering because the first inserted value determines the root.However, the left and right subtree elements do not necessarily need to appear in one fixed interleaving.For example, these sequences preserve the same relative order within each subtree:[3, 1, 2, 4, 5][3, 1, 4, 2, 5][3, 4, 1, 2, 5]The left-subtree sequence remains 1, 2, and the right-subtree sequence remains 4, 5.The elements from the two groups can be mixed together in different ways, provided that the relative insertion order within each group is preserved.This gives us the first major insight:Count the valid arrangements of the left subtree, count those of the right subtree, and then count the ways to interleave the two groups.Step 2: Why Do We Need Combinations (nCr)?Suppose a node has:L elements in its left subtree.R elements in its right subtree.After choosing the root, there are L + R remaining positions to fill.We need to choose which of those positions will contain the left-subtree elements. Once those positions are selected, the remaining positions automatically belong to the right subtree.The number of ways to choose L positions from L + R positions is: [(L+RL)][ \binom{L+R}{L} ][(LL+R​)] This is the familiar combinations formula, also written as nCr.The recursive count becomes: [ways=(L+RL)×waysLeft×waysRight][ ways = \binom{L+R}{L} \times waysLeft \times waysRight ][ways=(LL+R​)×waysLeft×waysRight] Here:waysLeft counts valid reorderings inside the left subtree.waysRight counts valid reorderings inside the right subtree.The combination term counts the possible interleavings of the two groups.All three factors are necessary.A small exampleConsider the tree formed by:nums = [2, 1, 3]There is one element on the left and one on the right.Therefore: [(21)=2][ \binom{2}{1}=2 ][(12​)=2] The two interleavings are:[1, 3][3, 1]Both produce the same BST when placed after root 2.Since each subtree contains only one element, each has exactly one valid arrangement.Thus: [ways=2×1×1=2][ ways = 2 \times 1 \times 1 = 2 ][ways=2×1×1=2] This count includes the original array. The final answer is: [2−1=1][ 2-1=1 ][2−1=1] The subtraction is performed only once, after the complete recursive count is calculated.Step 3: Calculating nCr EfficientlyNow we know how combinations fit into the solution. But how should the values of nCr be calculated?The mathematical formula is: [(nr)=n!r!(n−r)!][ \binom{n}{r}=\frac{n!}{r!(n-r)!} ][(rn​)=r!(n−r)!n!​] For example: [(42)=4!2!,2!=6][ \binom{4}{2}=\frac{4!}{2!,2!}=6 ][(24​)=2!,2!4!​=6] One approach is to calculate factorials repeatedly. However, the recursive solution needs combination values at many different subtree sizes. Recalculating factorials again and again adds unnecessary work.We can instead precompute all the required combinations using Pascal’s Triangle.The Pascal’s Triangle observationEvery value in Pascal’s Triangle is obtained by adding the two values directly above it: [(n−1r−1)+(n−1r)][\binom{n-1}{r-1} + \binom{n-1}{r} ][(r−1n−1​)+(rn−1​)] The boundary values are always 1: [(n0)=(nn)=1][ \binom{n}{0}=\binom{n}{n}=1 ][(0n​)=(nn​)=1] The first few rows look like this:11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1For example, the value 6 is calculated as:3 + 3 = 6It represents: [(42)=6][ \binom{4}{2}=6 ][(24​)=6] The same idea can be implemented using a two-dimensional list or array.Instead of calculating factorials whenever the recursive function needs a combination, we build the table once and look up the required value in constant time.How the submitted code builds the tableYour solution uses the list liss to store the rows of Pascal’s Triangle.for (int i = 0; i < nums.length; i++) {List<Integer> lis = new ArrayList<>();for (int j = 0; j < i + 1; j++) {if (i - 1 >= 0 && j - 1 >= 0 && j != i) {long sum = (liss.get(i - 1).get(j)+ liss.get(i - 1).get(j - 1));lis.add((int) (sum % mod));} else {lis.add(1);}}liss.add(new ArrayList<>(lis));}Each iteration builds one row.The first and last values of each row are 1. Every interior value is calculated by adding the two entries from the previous row.For instance, the row representing n = 4 contains:[1, 4, 6, 4, 1]So when the recursive function needs to choose positions for a left subtree of size 2 from a total of 4 elements, it can retrieve the value 6 directly.The table is built once before recursion begins.Step 4: Recursively Count the Left and Right SubtreesWith the combination table ready, the remaining work is recursive.Your sol() method starts by selecting the first element as the root:int root = nums.get(0);It then separates all remaining elements into two lists:List<Integer> left = new ArrayList<>();List<Integer> right = new ArrayList<>();for (int i = 1; i < n; i++) {if (nums.get(i) < root) {left.add(nums.get(i));} else {right.add(nums.get(i));}}Because the input contains distinct values, values smaller than the root belong to the left subtree, while larger values belong to the right subtree.For example:nums = [3, 4, 5, 1, 2]Root: 3Left: [1, 2]Right: [4, 5]Next, the function recursively counts the arrangements for both subtrees:long x = (sol(left)) % mod;long y = (sol(right)) % mod;The base case is:if (nums.size() <= 1) {return 1;}A subtree containing zero or one element has exactly one arrangement. There is nothing to reorder.Finally, the combination table is used to count the interleavings:long z = (liss.get(n - 1).get(left.size())) % mod;Here:n - 1 is the number of elements remaining after choosing the root.left.size() is the number of positions that must be assigned to the left subtree.z is the number of ways to choose those positions.The recursive result is then:return (int) ((((x * y) % mod) * z) % mod);In mathematical form: [ways=waysLeft×waysRight×(n−1leftSize)][ ways = waysLeft \times waysRight \times \binom{n-1}{leftSize} ][ways=waysLeft×waysRight×(leftSizen−1​)] The modulo operation keeps the intermediate result within manageable bounds.Complete Java SolutionThe following is the submitted solution, with formatting and explanatory comments added.class Solution {long mod = 1000000007;List<List<Integer>> liss = new ArrayList<>();public int sol(List<Integer> nums) {if (nums.size() <= 1) {return 1;}int root = nums.get(0);int n = nums.size();List<Integer> left = new ArrayList<>();List<Integer> right = new ArrayList<>();// Divide the remaining values by the current root.for (int i = 1; i < n; i++) {if (nums.get(i) < root) {left.add(nums.get(i));} else {right.add(nums.get(i));}}// Count valid arrangements of both subtrees.long x = sol(left) % mod;long y = sol(right) % mod;// Choose positions for the left-subtree elements.long z = liss.get(n - 1).get(left.size()) % mod;// Combine subtree arrangements and their interleavings.return (int) ((((x * y) % mod) * z) % mod);}public int numOfWays(int[] nums) {int n = nums.length;// Build Pascal's Triangle modulo 1,000,000,007.for (int i = 0; i < n; i++) {List<Integer> lis = new ArrayList<>();for (int j = 0; j <= i; j++) {if (i > 0 && j > 0 && j < i) {long sum = (long) liss.get(i - 1).get(j)+ liss.get(i - 1).get(j - 1);lis.add((int) (sum % mod));} else {lis.add(1);}}liss.add(lis);}List<Integer> num = new ArrayList<>();for (int value : nums) {num.add(value);}// Includes the original ordering.int ans = sol(num);// Exclude the original ordering.return ans - 1;}}Dry Run: How the Pieces Work TogetherConsider:nums = [2, 1, 3]1. Select the rootThe first element is 2.Root = 2Left = [1]Right = [3]2. Count the subtree arrangementsBoth subtrees contain one element.waysLeft = 1waysRight = 1The base case returns 1 for each subtree.3. Find the number of interleavingsThere are two remaining elements, and one belongs to the left subtree.The required combination is: [(21)=2][ \binom{2}{1}=2 ][(12​)=2] Pascal’s Triangle gives this value directly.4. Combine the results [ways=1×1×2=2][ ways = 1 \times 1 \times 2=2 ][ways=1×1×2=2] The two possible arrays are:[2, 1, 3][2, 3, 1]Both generate the same BST.5. Exclude the original orderingThe function initially counts all valid arrangements, including the input array.Therefore:Answer = 2 - 1 = 1The final output is 1, matching the expected result.Complexity AnalysisLet n be the length of nums.Building Pascal’s Triangle:There are (O(n^2)) entries, and each entry is calculated in constant time.Time: (O(n^2))Space: (O(n^2))Recursive BST counting:At each recursive call, the elements are divided into left and right lists. Across each level of the recursion, the elements processed total at most (n). In a highly unbalanced BST, the recursion can reach depth (n), and repeatedly scanning and copying the sublists can result in (O(n^2)) total work.Worst-case time: (O(n^2))Additional recursive and sublist space: up to (O(n^2)) across an unbalanced recursion, excluding the combination table.Therefore, the overall worst-case time complexity of this implementation is:O(n²)The Pascal’s Triangle table itself requires:O(n²) spaceThese bounds are suitable for the problem constraint of n <= 1000.Important Detail: Why Do We Subtract One?The recursive function counts all sequences that generate the same BST, including the original input sequence.However, the problem asks for the number of different reorderings, excluding the original ordering.That is why the final line is:return ans - 1;This subtraction should happen only once, after the full recursive count has been calculated. Subtracting one inside each recursive call would incorrectly exclude arrangements from individual subtrees.Interview TakeawayThis problem combines three ideas that are useful in more advanced algorithm questions:Recursive decomposition: The left and right subtrees can be solved independently.Combinatorics: The elements of the two subtrees can be interleaved in (\binom{L+R}{L}) ways.Dynamic programming: Pascal’s Triangle precomputes combination values so they can be reused instead of recalculated.The most important insight is that the left and right subtree sequences must each preserve their own relative order. Only their positions relative to one another can change.Once that restriction is understood, the counting formula follows naturally.ConclusionLeetCode 1569 looks difficult because it asks for the number of valid reorderings of an array, and the number of possible permutations grows extremely quickly.The solution becomes manageable when the problem is viewed through the structure of the BST. The first element fixes the root, smaller and larger elements form the left and right subtrees, and the two groups can be interleaved without changing the resulting tree.Recursion counts the valid arrangements inside each subtree, while combinations count the possible interleavings. Pascal’s Triangle makes those combination values available efficiently, and modular arithmetic keeps the calculations within the required range.The central formula to remember is:Ways =Left subtree ways× Right subtree ways× Ways to interleave both subtreesThis is the key to turning a seemingly enormous permutation problem into a structured recursive calculation.

LeetCodeJavaBinary Search TreeBSTRecursionCombinatoricsPascal TriangleDynamic ProgrammingDSAHard