I’ve always wanted to learn recursion but never actually went beyond fibonacci number and factorial, with lot more time on my hands due to lockdown tried to solve a few not so trivial problems.

  1. Permutations (https://leetcode.com/problems/permutations/)
given an array [1,2,3] find all permutations[
[1,2,3],
[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  • The idea is quite simple but let me explain how to think through this problem
  • Start with an empty array [ ]
  • Now _ _ _ in the first spot I can place any of the 3 numbers, I start with number 1.
  • 1 is rooted to the first spot so I can now chose the 2 or 3 (lets say 2) for the second spot and finally left with one option on the third spot.
class Solution {public List<List<Integer>> permute(int[] nums) {List<Integer> tmpList = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();backtrack(nums, tmpList, result);return result;}private void backtrack(int[] nums, List<Integer> tmpList, List<List<Integer>> result) {if (tmpList.size() == nums.length) {result.add(new ArrayList<>(tmpList));return;}for (int num: nums) {if (tmpList.contains(num))continue;tmpList.add(num);backtrack(nums, tmpList, result);tmpList.remove(tmpList.size()-1);}}}
  • We loop over our available options (1,2,3) and fill our temporary list making sure we don’t add the number which is already assigned.
  • And for every number we start a recursion tree by calling the function again, after assigning all the numbers to their respective slots, we exhaust our options and it’s time to fill our result
  • We add [1,2,3] to the result but starting with 1 we can also arrive at [1,3,2] to do this we remove 3 and then 2 from our temp list so that we can go down the next recursive path which is [1,3,2], this style of programming is called backtracking.
  • This is the most confusing part of this solution, if you look at the above code where we call backtrack function inside the for loop, after we add [1,2,3] to our result list, execution context of recursion returns to that line and we remove 3 from [1,2,3], remember this is the recursion stack which started with [1,2] we exhausted our options here as well since we added 3 (final option) to get to [1,2,3] so we backtrack again to our recursion stack started with [1], in this the iterator(for loop) is now at option 3, so we add [1,3] and start another branch of recursion giving us [1,3,2] and we finally remove [1] and go to recursion branch started with empty [ ] and add [2] (iterator in the for loop is at 2) to explore paths that start with 2 and so on.
  • Below is the recursion tree which makes things a little clear.

2. Unlocking a Safe

[X][2][3][4][X][6][7][8][9]Given a safe like above,Goal: Count of unique possible sequences given the following facts we know about the combination that will open the safe.Sequence starts at '2'.'1' and '5' are not used.We do not know the length 'n', but we will do examples of n==4.From one key to next is a chess knight-piece 'L' shaped move. In (x,y) that is (±2,±1) or (±1,±2).All possible sequences: 2727, 2927, 2929, 2729, 2767, 2943, 2949Total: 7

We can use the learnings from previous problem to solve this,

Our goal is to find all possible paths(unique) of size 4 starting from 2 moving like a knight

So if we start at 2 we can go to 7 or 9, lets say 7, from 7 we can come back to 2 which makes it 2727 (once such path of size 4)

But we want to explore other paths hence we remove the last number which is 7 to backtrack and explore a different path.

public class BreakSafe {int[][] grid = new int[][] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };int res = 0;public int breakSafe(int N) {List<Integer> tmpList = new ArrayList<>();tmpList.add(2);backtrack(0, 1, N, tmpList);return res;}private void backtrack(int i, int j, int N, List<Integer> tmpList) {if (tmpList.size() == N) {res++;return;}int[][] dirs = new int[][] { { -2, -1 }, { 2, -1 }, { -2, 1 }, { 2, 1 }, { 1, -2 }, { -1, 2 }, { -1, -2 },{ 1, 2 } };for (int[] dir : dirs) {int x = i + dir[0];int y = j + dir[1];if (x < 0 || y < 0 || x > 2 || y > 2 || grid[x][y] == 1 || grid[x][y] == 5)continue;tmpList.add(grid[x][y]);backtrack(x, y, N, tmpList);tmpList.remove(tmpList.size() - 1);}}}

We use directions 2D array to explore valid paths, if we land outside the board(boundary condition) or if we land on invalid keys (1 or 5) we just continue else we add the number at that location and go down the recursive path until we reach a path of size 4.

Below is the recursive tree.

3. 2 city Scheduling (https://leetcode.com/problems/two-city-scheduling/)

Input: [[10,20],[30,200],[400,50],[30,20]]Output: 110Explanation:The first person goes to city A for a cost of 10.The second person goes to city A for a cost of 30.The third person goes to city B for a cost of 50.The fourth person goes to city B for a cost of 20.The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.Note:1 <= costs[i][0], costs[i][1] <= 1000

Let’s use the recursive thinking developed over past few problems to solve this,

Decision choice:

At every level we have a decision to make out of 2 options

We either chose to assign a person to city A or city B

At first level we branch out these 2 options

idx=1 A=1 B=0 or idx=1 A=0 B=1

Important cases:

Index reaching the length of the array (exhausted all options so we return 1001 (more than max possible cost))

When A and B are equally assigned we return 0 (exhausted options and people are assigned equally)

We chose the minimum out of the two choices/branches and return it to previous call stack.

public int twoCitySchedCost(int[][] costs) {Map<String, Integer> cache = new HashMap<>();return backtrack(cache, costs, 0, 0, 0);}private int backtrack(Map<String, Integer> cache, int[][] costs, int A, int B, int i) {String key = A + "_" + B + "_" + i;if (cache.containsKey(key)) {return cache.get(key);}int N = costs.length / 2;if (A == N && B == N)return 0;if (i == costs.length)return 1001;int Achosen = backtrack(cache, costs, A + 1, B, i + 1);int Bchosen = backtrack(cache, costs, A, B + 1, i + 1);int minCost = Math.min(costs[i][0] + Achosen, costs[i][1] + Bchosen);cache.put(key, minCost);return minCost;}

Recursive tree:

Notice how we reach (3,2,1) from (2,2,0) and (2,1,1) for this very reason we use caching, if we cache results for a given key (i + A + B) we can lookup our cache to retrieve these values instead of going through the tree all over again.

This approach is generally called Top-down Dynamic Programming.

That’s all for this post, I’ll be writing more as I learn :)

References:

Programming, Soccer, gaming, photography, food and drinks 😊

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store