DAY 19 : Solved Letter Combinations, Permutations, and Palindrome Partitioning with Recursion | My DSA Journey - Recursion

---

Introduction

Welcome to Day 19 of my DSA Journey!
Over the past few weeks, I’ve been diving deep into one of the most fundamental and important concepts in DSA — Recursion.

I’ve worked through a collection of classic problems centered around recursion and backtracking — two core concepts essential to mastering Data Structures and Algorithms.

I'm documenting my journey publicly to stay consistent and help others who are also learning DSA from scratch.

Here’s what I learned over the last 3 days:

Day 16
→ Letter Combination of a Phone Number
→ Dice Throw

Day 17
→ Permutations
→ Backtracking with Visited Tracking (Boolean Array Approach)
→ Backtracking with In-Place Swapping Approach

Day 18
→ Palindrome Partitioning

Let’s break down each of these topics below 👇

---

Q 1. Letter Combination of a Phone Number:

Given a string containing digits from 2 to 9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

Each digit maps to a set of letters like on a traditional phone keypad:

2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> pqrs
8 -> tuv
9 -> wxyz

Example:

Input: digits = '23'
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Explanation:

• The digit '2' corresponds to the letters "abc".
• The digit '3' corresponds to the letters "def".

We want to generate all combinations where:

• The first character comes from "abc" (for digit 2), and
• The second character comes from "def" (for digit 3).

Let's break it down:

• From 'a' (from 2) → combine with 'd', 'e', 'f' → "ad", "ae", "af"
• From 'b' → "bd", "be", "bf"
• From 'c' → "cd", "ce", "cf"

That gives us: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Approach:

We can solve this using recursion and backtracking:

1. Start with an empty string p (processed part).
2. At each digit in the input up (unprocessed part), fetch the corresponding characters from the keypad.
3. For each character:
   • Append it to the processed string p.
   • Recursively call the function with the remaining digits (up).
4. When there are no more digits left in up, the processed string p is a valid combination and should be added to the result list.

Recursive Tree Visualization:

Let's visualize the recursion tree for input "23":

                          ""
                         / | \
                       a   b   c     ← from digit '2'
                    / | \ /|\ /|\
                  d  e  f...       ← from digit '3'

→ Final combinations:
  "ad", "ae", "af", 
  "bd", "be", "bf", 
  "cd", "ce", "cf"

At each level:

• We choose a letter from the current digit.
• Recurse on the rest of the digits.
• When up is empty, we have a valid combination.

Code:

public class Main {
    public static void main(String[] args) {
        String str = "23";
        String[] lettersArr = {
            "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        List<String> ans = new ArrayList<>();
        combination("", str, lettersArr, ans);
        System.out.println(ans);
    }

    static void combination(String p, String up, String[] lettersArr, List<String> ans){
        if (up.isEmpty()) {
            if (!p.isEmpty()) {
                ans.add(p);
            }
            return;
        }

        int digit = up.charAt(0) - '0';
        String str = lettersArr[digit - 2];

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            combination(p + ch, up.substring(1), lettersArr, ans);
        }
    }
}

Key Takeaways:

• This problem is a great example of backtracking.
• Focus on separating the processed and unprocessed parts of the string during recursion.
• Try drawing the recursive tree to better understand the flow and how combinations are built step-by-step.

---

Q 2. Dice Throw:

Given a number n, return a list of all possible sequences of dice rolls (1 to 6) that sum up to n.

• Each roll can be from 1 to 6.
• We can roll the dice multiple times.
• The order of rolls matters.

Example:

Input: n = 4
output: ["1111", "112", "121", "13", "211", "22", "31", "4"]

Explanation:

We are looking for all sequences of dice rolls that sum up to 4. Let's break it down:

• "1111" → 1 + 1 + 1 + 1 = 4
• "112" → 1 + 1 + 2 = 4
• "121" → 1 + 2 + 1 = 4
• "13" → 1 + 3 = 4
• "211" → 2 + 1 + 1 = 4
• "22" → 2 + 2 = 4
• "31" → 3 + 1 = 4
• "4" → 4 = 4

All combinations are valid sequences of dice rolls that add up to 4.

Approach:

We can solve this using recursion and backtracking:

1. Start with an empty string p that represents the current sequence of dice rolls.
2. At each step:
   • Try all possible dice rolls (from 1 to 6).
   • Only consider rolls that do not exceed the remaining target (up).
3. For each valid roll:
   • Append the roll to the current sequence.
   • Recurse with the remaining sum (up - i).
4. If up == 0, we have found a valid combination. Return it.

Recursive Tree Visualization:

Here’s a simplified version of the recursive tree for n = 2:

          ""
        /  |  \
      1    2   3  ... (up to 6 but only 1 & 2 are valid for n = 2)
     |     |
    11    12   ← valid when sum reaches 2

So the output will be:

["11", "2"]

Code:

public class Main {
    public static void main(String[] args) {
        int n = 4;

        ArrayList<String> result = diceList("", n);
        System.out.println(result);
    }

    static ArrayList<String> diceList(String p, int up) {
        if (up == 0) {
            ArrayList<String> list = new ArrayList<>();
            list.add(p);
            return list;
        }

        ArrayList<String> ans = new ArrayList<>();
        for (int i = 1; i <= 6 && i <= up; i++) {
            ans.addAll(diceList(p + i, up - i));
        }
        return ans;
    }
}

Key Takeaways:

• This problem is an excellent exercise for generating combinations with constraints.
• It shows how recursion can be used to explore multiple paths.
• The stopping condition (up == 0) defines when a complete valid combination is found.
• Try visualizing the recursive calls to understand how the recursion tree unfolds.

---

Q 3. Permutations - Visited Tracking Approach:

Given an array of distinct integers, return all possible permutations of the array.

Each permutation should be a unique arrangement of the elements in the array.

Example:

Input: arr = [1, 2, 3]
Output:
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]

Explanation:

We are asked to generate all permutations of the array [1, 2, 3].

There are 3! = 6 possible ways to arrange the elements:

• Starting with 1: → [1,2,3], [1,3,2]
• Starting with 2: → [2,1,3], [2,3,1]
• Starting with 3: → [3,1,2], [3,2,1]

Each of these is a unique permutation of the original array.

Approach:

We can solve this using recursion and backtracking:

1. Maintain a temporary list list that stores the current permutation being formed.
2. Keep a boolean array mark to track which elements have been used.
3. For every unused element:
   • Mark it as used.
   • Add it to the current permutation.
   • Recursively call the function to fill the next position.
   • Backtrack by removing the element and marking it as unused again.
4. When the length of list equals the array length, we have a valid permutation.

Recursive Tree Visualization:

Here's a simplified view of the recursive tree for the input [1, 2]:

          []
       /      \
     [1]      [2]
     /          \
  [1,2]        [2,1]

At each level, we add an unused number to the list. When all numbers are used, we store that combination.

Code:

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        boolean[] mark = new boolean[arr.length];

        List<List<Integer>> ans = new ArrayList<>();
        permutation(new ArrayList<>(), arr, ans, mark);
        System.out.println(ans);
    }

    static void permutation(List<Integer> list, int[] arr, List<List<Integer>> ans, boolean[] mark) {
        if (list.size() == arr.length) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!mark[i]) {
                list.add(arr[i]);
                mark[i] = true;

                permutation(list, arr, ans, mark);

                list.removeLast();  // Backtrack
                mark[i] = false;
            }
        }
    }
}

Key Takeaways:

• This problem is a textbook example of backtracking.
• Using a mark[] array helps track which elements have already been used in the current permutation.
• Recursive calls explore all possible orders by trying every choice at each step.
• Backtracking ensures we undo choices to explore different paths and avoid duplicates.
• It's excellent practice for understanding decision trees and depth-first search (DFS) logic.

---

Q 4. Permutations - In-Place Swapping Approach:

In the previous section, we solved the Permutations problem using backtracking with a boolean mark[] array to track used elements.

In this version, we'll solve the same problem — generating all possible permutations of an array — but using a different and more in-place approach by swapping elements.

What’s Different?

• Instead of maintaining a separate boolean array to track usage, we swap elements directly in the array to simulate different arrangements.
• This is more memory-efficient and avoids using extra space for tracking.

Example:

Input: arr = [1, 2, 3]
Output:
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]

We generate all permutations by fixing one element at a time and swapping to bring all other elements into that position recursively.

Approach (In-Place Swapping) :

1. Use an index pointer to determine the current position to fill.
2. For each index from index to end of array:
   • Swap the current element with the element at the current index.
   • Recurse for the next index (index + 1).
   • Backtrack by swapping the elements back.
3. When index == arr.length, we’ve formed one valid permutation.

Recursive Tree Visualization:

For input [1, 2, 3], the recursion tree (simplified view) would look like:

         [1,2,3] (index=0)
        /    |    \
    [1,2,3][2,1,3][3,2,1]  ← index=1
     ...

• At each level, we swap the index element with each subsequent element.
• We then move deeper into the recursion to fix the next index.
• Backtracking ensures the original array is restored after each recursive call.

Code:

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};

        List<List<Integer>> ans = new ArrayList<>();
        permutation(arr, 0, ans);
        System.out.println(ans);
    }

    static void permutation(int[] arr, int index, List<List<Integer>> ans) {
        if (index == arr.length) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int num : arr) {
                list.add(num);
            }
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < arr.length; i++) {
            swap(arr, index, i);
            permutation(arr, index + 1, ans);
            swap(arr, index, i); // Backtrack
        }
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Key Takeaways:

• This approach avoids extra space for tracking used elements by using in-place swapping.
• The core logic remains the same: recursively build all possible arrangements.
• Great for understanding backtracking through index manipulation.
• More efficient in terms of space, especially for large inputs.

---

Q 5. Palindrome Partitioning:

Given a string str, return all possible palindromic partitions of the string.

Each partition should be a list of substrings such that every substring is a palindrome.

Example:

Input: str = "aab"
Output:
[
["a", "a", "b"],
["aa", "b"]
]

Explanation:

We're asked to split the string "aab" into all possible sets of substrings where each substring is a palindrome:

• "a", "a", and "b" are all individually palindromes → ["a", "a", "b"]
• "aa" is a palindrome, and "b" is a palindrome → ["aa", "b"]

These are the only valid palindrome partitions.

Approach:

We solve this problem using backtracking with string slicing:

1. Start from index 0 of the string.
2. Try all possible substrings starting from index.
3. For each substring:
   • Check if it is a palindrome.
   • If yes, add it to the current list.
   • Recurse from the next index (i + 1).
   • Backtrack by removing the last added substring.
4. When index reaches the end of the string, add the current list as one valid partition.

Recursive Tree Visualization:

For input "aab", here’s a simplified recursive tree:

              []
             /    
          ["a"]         
         /     \
     ["a","a"]   ["aa"]
      /             \
["a","a","b"]     ["aa","b"]

Each level represents a decision to cut a substring and check if it's a palindrome. Valid paths are collected as answers.

Code:

public class Main {
    public static void main(String[] args) {
        String str = "aab";

        List<List<String>> ans = new ArrayList<>();
        partition(new ArrayList<>(), str, ans, 0);
        System.out.println(ans);
    }

    private static void partition(List<String> list, String str, List<List<String>> ans, int index) {
        if (index == str.length()) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < str.length(); i++) {
            String sub = str.substring(index, i + 1);
            if (isPalindrome(sub)) {
                list.add(sub);
                partition(list, str, ans, i + 1);
                list.removeLast(); // Backtrack
            }
        }
    }

    private static boolean isPalindrome(String sub) {
        int s = 0;
        int e = sub.length() - 1;

        while (s < e) {
            if (sub.charAt(s) != sub.charAt(e)) {
                return false;
            }
            s++;
            e--;
        }
        return true;
    }
}

Key Takeaways:

• This problem is a strong example of backtracking with constraints.
• Use substring slicing to explore different partition options.
• Always check for palindromes before diving deeper into recursion.
• Recursion builds partitions step-by-step; backtracking helps revert choices.
• Helps understand how to combine logic + recursion + validation in one solution.

---

What's next:

I’m continuing this journey and will be:

• Posting blogs every 3 days.

• Also learning Web Development — check out my Web Dev Journey Blog.

• You can follow my journey on X (Twitter) where I post regular updates.

---

Conclusion:

In this blog of my dsa journey, we explored some foundational backtracking and recursion problems that form the core of many algorithmic challenges:

• 📱 Letter Combination of a Phone Number – converting digits into all possible letter sequences.
• 🎲 Dice Throw – generating all combinations of dice rolls that sum to a target.
• 🔁 Permutations – creating all possible orderings of elements using two powerful approaches:
  • Visited tracking with a mark[] array
  • In-place swapping for space-efficient recursion
• 🔤 Palindrome Partitioning – partitioning a string such that every segment is a palindrome.

Each problem reinforced important problem-solving skills like decision making, recursive tree traversal, and backtracking with constraints.

If you're learning DSA, mastering these problems helps build strong intuition for breaking problems down recursively and thinking in terms of state, choice, and constraints.
If you're on a similar journey, feel free to reach out or follow along — we’re all in this together.