Skip to main content

Recursion

  • Understanding recursion
  • Solved problems are presented in alphabetical order
Binary Tree Right Side View
Construct Binary Tree from Preorder and Inorder Traversal
Letter Combinations of a Phone Number
Lowest Common Ancestor of a Binary Tree
Permutations

↗ See LeetCode Problem #46​

import java.util.List;import java.util.ArrayList;import java.util.Deque;import java.util.ArrayDeque;public class Solution {    public static List<List<Integer>> permute(int[] nums) {        int leftIndex = 0;        int matchedIndex = 0;        List<Integer> matchedList = new ArrayList<>();        List <List<Integer>> resultLists = new ArrayList<>();                //  Output list of lists to be returned        List<List<Integer>> outputPermutations = new ArrayList<>();        //  Queue to create a list of all permutations        Deque<List<Integer>> allPermutations = new ArrayDeque<>();        //  Add (to the list of all permutations) an empty list first        allPermutations.add(new ArrayList<>());        for (int currentElement : nums) {            int sizeAllPermutations = allPermutations.size();            for (int i = 0; i < sizeAllPermutations; i++){                //  Remove and store that last (old) permutation                List<Integer> oldPermutation = allPermutations.poll();                //  Create new permutation                //  Add the currentElement at every index                for (int j = 0; j <= oldPermutation.size(); j++) {                    List<Integer> newPermutation = new ArrayList<>(oldPermutation);                    newPermutation.add(j, currentElement);                    if (newPermutation.size() == nums.length) {                       outputPermutations.add(newPermutation);                    } else {                        allPermutations.add(newPermutation);                    }                }            }        }        return outputPermutations;    }    public static void main(String[] args) {        // Example 1:        int[] nums1 = {1,2,3};        //  O/P: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]        // Example 2:        int[] nums2 = {0,1};        //  O/P: [[0,1],[1,0]]        // Example 3:        int[] nums3 = {1};        //  O/P: [[1]]        System.out.println(permute(nums1));        System.out.println(permute(nums2));        System.out.println(permute(nums3));    }}
Subsets

↗ See LeetCode Problem #78​

import java.util.List;import java.util.ArrayList;public class Solution {    public static List<List<Integer>> subsets(int[] nums) {        //  Using Breadth First Search approach        //  Declare the ouput set that is the set of all sets        List<List<Integer>> outputSet = new ArrayList<>();        //  Add an empty subset to the output list        outputSet.add(new ArrayList<>());        for (int currentElement : nums) {            //  Store the size of the current output set            int currentSize = outputSet.size();            //  Add the current element to the existing subsets            //      in the current output set            for (int i = 0; i < currentSize; i++) {                //  Declare the new subset created with current subset                //      element from the output set                List<Integer> newSubset =                        new ArrayList<>(outputSet.get(i));                //  Add the current element from the given array (nums)                //      to the new subset                newSubset.add(currentElement);                //  Add the new subset to the output list                outputSet.add(newSubset);            }        }        return outputSet;    }    public static void main (String[] args) {        // Example 1:        int[] nums1 = {1,2,3};        //  O/P: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]        // Example 2:        int[] nums2 = {0};        //  O/P: [[],[0]]        System.out.println(subsets(nums1));        System.out.println(subsets(nums2));    }}
Two Sum IV - Input is a BST