Recursion and backtracking

What is recursion?

Recursion is a program where the function calls itself. It has the following two parts

1. The base case so that the function can stop calling itself to exit from the loop.
2. Recursion case so that function can call itself.

To analyze the recursion code, we need to understand the following.

1. Recursion code.

const fact = n=> {
  if(n  == 0) {
    return 1;
  }
  return n * fact(n-1);
}

2. Dependency tree/ recursion tree

3. Recursion simulation/recursion sketch

Bruteforce and backtracking

1. Bruteforce means exploring every possible area.
2. Backtracking is implementation.

Let’s try to solve few recursion problems.

GCD of two a & b

Every number a can be represented as below

a = b*q + r

Where, 
b = divisor
q = quotient 
r = remainder 

As per the Euclidian algorithm, the GCD of (a,b) is equal to (b, r) i.e (b, a%b) . Based on this we can write code as below.

const gcd = (a, b) => {
  if(b == 0) {
    return a;
  }
  return gcd(b, a % b);
}

Following is the recursion tree for example gcd(6,4) .

Fibonacci number

Following is the code for the Fibonacci number.

const fib = n => {
  if(n < 2) {
    return n;
  }
  return fib(n-1) + fib (n-2);
}

Following is the recursion tree for example fib(5) .

Note 1: Use https://visualgo.net/en/sssp to visualize the code

Note 2: To visualize running code https://pythontutor.com/render.html#mode=display

N Queens

Condition to diagonally attack using slope equation.

Find all subsequence of the array

Tower of Hanoi

Tower of Hanoi

The goal is to transfer x discs from peg A to C with the help of an extra peg B i.e need to find f(x,A,C,B).

1. Transfer x-1 discs from A to B i.e. run f(x-1, A, B, C) function with extra C.
2. Transfer the last disc from A to C
3. Transfer x-1 discs from B to C i.e. run f(x-1, B, C, A) function with extra A .

Following is the recursion code to solve this.

const towerOfHanoi = (x, source, target, aux) => {
  // Base case
  if(x == 0) {
    return;
  }
  towerOfHanoi(x-1, source, aux, target);
  console.log(`Move disc ${x} from ${source} to ${target}`);
  towerOfHanoi(x-1, aux, target, source);
  
}
towerOfHanoi(4, 'A', 'C', 'B');

Kth move in Tower of Hanoi problem

1. Every recursion branch takes care of certain parts of moves.
2. To find out kth move, we need to find out which branch kth move will lie.

Let’s say for x=3 , there would be moves for x=2 at the first recursion, one moves in the middle and again x=2 at the bottom recursion.

Q. When you are at f(x) for kth move, how do you decide which branch you need to take?

Ans. If we know the number of moves for each branch then we can see which branch we should take for kth move.

Let’s say for x=3 and k=6 , we can take the last recursion branch.

Note: Once you decide on the branch then you need to reduce the moves covered by the earlier branch. I.e. in the above example, once it chooses the bottom recursion, k=6 the value will be reduced by 6 — 3 — 1 = 2 .

Now let’s count the number of moves for f(x) . If we just focus on x then we have the following recursion.

f(x) = f(x-1) + 1 + f(x-1)
f(x) = 2 * f(x-1) + 1
f(1) = 1
f(2) = 2 * f(1) + 1 = 2 + 1 = 3
f(3) = 2 * f(2) + 1 = 2 * 3 + 1 = 7
f(x) = 2^n - 1

Based on the above we can write the following code.

const kthMovetowerOfHanoi = (x, source, target, aux, k) => {
  // Base case
  if(x == 0) {
    return;
  }
  const moves = 1<<(x-1) - 1; // Moves for (x-1) branch
  // check if kth move falls into first recursion
  if(k <= moves) {
    kthMovetowerOfHanoi(x-1, source, aux, target, k);
    return;
  }
  // Check if kth moves match here
  if(k == moves + 1) {
    console.log(`Move disc ${x} from ${source} to ${target}`);
    return;
  }
  // Check the if kth moves fall into last recursion then reduce total so far
  kthMovetowerOfHanoi(x-1, aux, target, source, k - moves + 1);
}
towerOfHanoi(4, 'A', 'C', 'B', 6);

Permutation

https://leetcode.com/problems/permutations/

Approach 1: Generate permutations as per the input order (more useful approach)

1. Build a frequency map for each number.
2. For each level, we have the option to choose the element as per frequency.
3. If a valid choice then use it otherwise try the next number.
4. Move to the next level.
5. This generates the permutations as per the order.

Following is the code to implement this logic.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    const n = nums.length;
    const map = new Map();
    for (const num of nums) {
        map.set(num, map.has(num)? map.get(num) + 1: 1);
    }
    const ans = [];
    const result = [];
    const recursion = i => {
        if (i === n) { // Base case to check for answer
            ans.push([...result]);
            return;
        }
        // Try all possible choices from map for ith position
        for (const [num, frequency] of map) {
            // In case of invalid choice, skip
            if (frequency === 0) {
                continue;
            }
            map.set(num, frequency - 1); // num is used once so reduce freq
            result.push(num);
            recursion(i + 1); // Try for next position
            map.set(num, frequency); // undo i.e. backtrack
            result.pop(); // undo i.e. backtrack
        }
    }
    recursion(0);
    return ans;
};

Approach 2: Generate permutations without order

Following is code to generate in-place permutation which doesn’t guarantee the order.

const permutation = (nums, i) => {
  const n = nums.length;
  // Base case
  if(i === n) {
    // print ans
    console.log(nums);
  }
  // We have i....n-1 choices to choose at this place
  for (let j=i; j < n; j++) {
    swap(nums, i, j);
    permutation(nums, i + 1, ans);
    swap(nums, i, j); // undo
  }
}
permutation([1,2,3,4],0);

Kth permutation

https://leetcode.com/problems/permutation-sequence/

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: "213"

Approach

To find the kth permutation, we will apply logic similar to the kth move for the tower of Hanoi.

1. For f(n) find out the number of possible permutations. It is n! .
2. For given kth , now let’s find which recursion branch it would pick.
3. Reduce the k value for all the above recursion branches skipped before choosing the branch suitable for kth .

Following is a flow to showcase above.

Following is the code to implement this algorithm.

const fact = n => {
    const ans = new Array(n + 1).fill(1);
    // base case: n=0 & n=1, fact= 1
    for (let i = 2; i < n + 1; i++) {
        ans[i] = i * ans[i - 1];
    }
    return ans;
}
/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
    const nums = new Array(n).fill(0).map((a, i) => i + 1);
    const FACT = fact(n);
    const result = [];
    const generatePermutations = (nums, k) => {
        const n = nums.length;
        if (n === 0) { // Base case 
            return;
        }
        // contribution of one branch
        const moves = FACT[n - 1];
        const index = Math.floor((k - 1) / moves);
        const [num] = nums.splice(index, 1); // Remove one elem at index
        result.push(num);
        const left = k - (moves * index);
        generatePermutations(nums, left); // Now solve for next position
    }
    generatePermutations(nums, k);
    return result.join('');
};

Next permutation

https://leetcode.com/problems/next-permutation/description/

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Approach

1. If given sequence (for example [9, 5, 4, 3, 1]) is in decreasing order then no next larger permutation is possible.
2. We can apply above observation on given sequence to find the first pair of two successive numbers a[i] and a[i−1], from the right, which satisfy a[i]>a[i−1] .
3. No rearrangements to the right of a[i−1] can create a larger permutation since that subarray consists of numbers in descending order.
4. Therefore, we need to rearrange the numbers to the right of a[i−1] including itself.
5. Q. What kind of rearrangement will produce the next larger number?
6. We want to create the permutation just larger than the current one.
7. Therefore, we need to swap the number a[i−1] with the number which is just larger than a[i−1] among the numbers lying to its right section, say a[j].
8. We now have the correct number at index i−1. But still the current permutation isn’t the permutation that we are looking for.
9. We need the smallest permutation that can be formed by using the numbers only to the right of a[i−1].
10. Therefore, we need to place those numbers in ascending order to get their smallest permutation.
11. But, recall that while scanning the numbers from the right, we simply kept decrementing the index until we found the pair a[i] and a[i−1] where, a[i]>a[i−1].
12. Thus, all numbers to the right of a[i−1] were already sorted in descending order.
13. Furthermore, swapping a[i−1] and a[j] didn’t change that order.
14. Therefore, we simply need to reverse the numbers following a[i−1] to get the next smallest lexicographic permutation.

Following is code for reference.

const swap = (nums, i, j) => {
    [nums[i],nums[j]] = [nums[j], nums[i]];
}
const reverse = (nums, i, j) => {
    while(i < j) {
        swap(nums, i, j);
        i++;
        j--;
    }
}
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    const n = nums.length;
    // find peak by traversing from right to left 
    let i=n - 1;
    while(i > 0 & nums[i-1] >= nums[i]) {
        i--;
    }
    // Entire sequence is in decreasing order then simply reverse and return it
    if(i === 0) {
        return reverse(nums, 0, n-1);
    }
    
    // Get the next sequence by comparing pivot i -1
    const pivot = nums[i-1];
    
    // Get next immediate number greater than pivot from right to left
    let j = n-1;
    while(j > i && nums[j] <= pivot) {
        j--;
    }
    // swap pivot with j
    swap(nums, i-1, j);
    
    // Revrese slope of peak
    reverse(nums, i, n-1);
};

Subsets

78. Subsets

https://leetcode.com/problems/subsets/description

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Approach

We can use recursion to generate all the possible subset.

const subsetHelper = (nums, i, partial, ans) => {
    // base case: leaf node i.e. empty problem
    if (i == nums.length) {
        ans.push([...partial]); // Copy into final answer
        return;
    }

    // exclude item
    subsetHelper(nums, i + 1, partial, ans);

    // include item
    partial.push(nums[i]);
    subsetHelper(nums, i + 1, partial, ans);
    partial.pop(); // clean it for next node
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
    const ans = [];
    subsetHelper(nums, 0, [], ans);
    return ans;
};

90. Subsets II

https://leetcode.com/problems/subsets-ii/description

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Approach

Once number is used then special check is needed to skip the duplicates. To write the cleaner code, le’ts perform ignore step after the choose step.

Also, need to sort the nums so that we can apply duplicate check easily.

const recursion = (nums, i, slate, output) => {
    // base case: for leaf node
    if(i === nums.length) {
        output.push([...slate]);
        return;
    }
    
    // choose i
    slate.push(nums[i]);
    recursion(nums, i+1, slate, output);
    slate.pop(); // remove for cleanup
    
    // ignore all duplicates
    while(nums[i] === nums[i+1]) {
        i++;
    }
    
    // ignore i
    recursion(nums, i+1, slate, output);
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    nums.sort((a, b) => a - b)
    const output = [];
    recursion(nums, 0, [], output);
    return output;
};

Find N to divide two number representation

1. We have given an array of chars [a,b,c,d,e,f,g,h,i,j] of fix length 10which can map to 10unique digits [5,1,3.......] .
2. For givenN which can be defined asN=abcde/fghij
3. Find out number of possible assignments of digits to chars array so that it can satisfies N relationship.

Approach

1. Check what all options are possible
2. Check for constraints.

In this example, we have following constraints.

1. All char should map to unique digits
2. N=abcde/fghij

Use constraints to do following

1. Define generator to generate the option
2. Use condition to validate the option

Generally generator are slow and validator is faster. So which constraints should be used as generator vs validator?

Option1: Use unique digits to generate 10! numbers and N condition to validate.

Option2: Use N to generate numbers and unique digits to validate. To generate numbers, first we will generate all possible numbers for ghijk which will be 10^5 as each char can be placed by 10 options. Then abcdef can be generated by multiplication abcdef=N*ghijk (Or we can reverse the order).

Between 10!and10^5 , obviously second is better but let’s write code for both.

Following is implementation for option#1.

const next_permutation = (arr) => {
 ...
 ...
}
const option1 = (chrs, N) => {
  let count = 0;
  const arr = [0,1,2,3,4,5,6,7,8,9];
  const MAX = 9876543210;
  do {
    const abcde = 10000*arr[0] + 1000*arr[1] + 100*arr[2] * 10*arr[3] * arr[4];
    const fghij = 10000*arr[0+5] + 1000*arr[1+5] + 100*arr[2+5] * 10*arr[3+5] * arr[4+5];
    if(abcde/fghij == N) {
       count++;
    }
  } while(next_permutation(arr, MAX);
  return count;
}

Following is implementation for option#2.

const option2 = (chrs, N) => {
   /**
    abcde = (01234,98765)
    fghij = (01234, 98765)/N
    Choose smaller to loop, here fghij is the smaller
   */
   let count = 0;
  for (let fghij = 1234; fghij <= 98765/N; fghij++) {
      const abcde = fghij * N;
      // Check for constraints
      const set = new Set([
                            ...abcde.toString().split(''),
                            ...fghij.toString().split('')
                           ]);
      if(set.size === 10) {
        count++;
      }
  }
  return count;
}

K-knights

Number of ways to place k- knights on n*n chess board.

Let’s come up with following

1. Level — Define choice structure.
2. How to maintain knights.

Option #1: Use K Knights as level

1. Level: Use k knights as level.
2. For each knight, the whole board is a choice.
3. Once the one knight is placed, move to the next knight.

Following is the code to implement this approach.

const solve = (n) => {
  const board = new Array(n).fill(0).map(a => new Array(n).fill(0);
  let ans = 0;
  const check = (i, j) => {
    const dx = [1, 2,-1, -2,-1, -2, 1, 2];
    const dy = [2, 1,-2, -1, 2, 1, -2, -1];
    for (let pos = 0; pos < 8; pos++) {
      const nx = i + dx[pos];
      const ny = j + dy[pos];
      // Check if (nx,ny) cell is getting attacked by (i,j)
      if(nx >=0 && nx < n && ny >=0 && ny < n && board[nx][ny] !== 0) {
          return false;
      }
    }
    return true;
  }
  const recursion = (level) => {
    // Base case
    if(level ===n) {
      ans++;
      return;
    }
    // Try to place knight on all the places in the board
    for (let i=0; i < n; i++) {
      for (let j=0; j < n; j++) {
          if(check(i,j)) {
              board[i][j] = 1;
              recursion(level + 1);
              board[i][j] = 0; // undo
          }
      }
    }
  }
  recursion(n);
  return ans;
}

Time complexity calculation

1. For each knight, we have options to place on board.
2. This may lead to duplicate placement (as knights are not numbered)
3. Therefore we need to divide it by k! to get the unique count.

4. For the first knight, there are n*n options

5. For the second knight there are n*n-1 options.

6. For the third knight there are n*n -2 options.

7. For kth knight there are n*n — k -1 options.

8. Time complexity of code is P(N*N, k)

Can we optimize it further?

One approach is, not to generate a duplicate solution. We can try to place k1 knights before k2

We can update the code below to implement this optimization using lastX and lastY .

const solve = (n) => {
  const board = new Array(n).fill(0).map(a => new Array(n).fill(0);
  let ans = 0;
  const check = (i, j) => {
    const dx = [1, 2,-1, -2,-1, -2, 1, 2];
    const dy = [2, 1,-2, -1, 2, 1, -2, -1];
    for (let pos = 0; pos < 8; pos++) {
      const nx = i + dx[pos];
      const ny = j + dy[pos];
      // Check if (nx,ny) cell is getting attacked by (i,j)
      if(nx >=0 && nx < n && ny >=0 && ny < n && board[nx][ny] !== 0) {
          return false;
      }
    }
    return true;
  }
  const recursion = (level, lastX, lastT) => {
    // Base case
    if(level ===n) {
      ans++;
      return;
    }
    // Try to place knight on all the places in the board
    for (let i=0; i < n; i++) {
      for (let j=0; j < n; j++) {
          if(i === lastX && j === lastY) {
            continue;
          }
          if(check(i,j)) {
              board[i][j] = 1;
              recursion(level + 1, i, j);
              board[i][j] = 0; // undo
          }
      }
    }
  }
  recursion(n,0, -1);
  return ans;
}

We can further optimize it by only checking the last four cells.

i.e. keep dx & dy as below.

const dx = [-1, -2,-1, -2];
const dy = [-2, -1, 2, 1];

Similar closed formula

A172134 - OEIS

Number of ways to place 3 nonattacking knights on an n X n board.

Option 2: Choose each cell as level to place or not to place knight

Following is the code to implement option#2.

const solve = (n) => {
  const board = new Array(n).fill(0).map(a => new Array(n).fill(0);
  let ans = 0;
  const check = (i, j) => {
    const dx = [1, 2,-1, -2,-1, -2, 1, 2];
    const dy = [2, 1,-2, -1, 2, 1, -2, -1];
    for (let pos = 0; pos < 8; pos++) {
      const nx = i + dx[pos];
      const ny = j + dy[pos];
      // Check if (nx,ny) cell is getting attacked by (i,j)
      if(nx >=0 && nx < n && ny >=0 && ny < n && board[nx][ny] !== 0) {
          return false;
      }
    }
    return true;
  }
  const recursion = (level, knights) => {
    // Base case
    if(level ===n*n || knights === 0) {
      if(knights === 0) {
          ans++;
      }
      return;
    }
    int row= Math.floor(level/n);
    int col= level % n;
    // Choice to skip cell
    recursion(level+1, knights);
    // Choice to place knight on cell
    if(knights & check(row, col)) {
      board[row][col] = 1;
      recursion(level + 1, knights - 1);
      board[row][col] = 0;
    }
  }
  recursion(0, k);
  return ans;
}

Time complexity: O(2^(n*n))

Sudoku

https://leetcode.com/problems/sudoku-solver

Following is the board start state.

The goal here is to fill in numbers to satisfy the following rules.

1. Each 3*3 grid should have a number form 1 to 9.
2. Each row should have a number from 1 to 9
3. Each column should have a number from 1 to 9.

Based on this, we can fill the grid.

Solution

Let’s apply the level, choice, check, and move approach.

To apply the check, the complex part is to validate the 3*3 grid in the 9*9 problem. So the goal is to find out the starting index of the 3*3 grid. We can use floor(x/3)*3 to get the index of the starting cell. This is based on the following.

Following is the code to implement this approach.

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
    let isSolved = false;
    const n = board.length;
    const cellSize = Math.sqrt(n);
    const isValid = (level, num) => {
        const i = Math.floor(level / n);
        const j = level % n;
        // Check for row
        for (let p = 0; p < n; p++) {
            if (p === j) {
                continue;
            }
            if (board[i][p] === num) {
                return false;
            }
        }
        // Check for column
        for (let p = 0; p < n; p++) {
            if (p === i) {
                continue;
            }
            if (board[p][j] === num) {
                return false;
            }
        }
        // Check square grid
        const p = Math.floor(i / cellSize) * cellSize;
        const q = Math.floor(j / cellSize) * cellSize;
        for (let x = p; x < p + cellSize; x++) {
            for (let y = q; y < q + cellSize; y++) {
                if (x === i && y === j) {
                    continue;
                }
                if (board[x][y] === num) {
                    return false;
                }
            }
        }
        return true;
    }
    const recursion = level => {
        const i = Math.floor(level / n);
        const j = level % n;
        // Base case
        if (level === n * n) {
            return;
        }
        // if board is empty then apply all choices
        if (board[i][j] === '.') {
            // Apply all choices
            for (let x = 1; x <= n; x++) {
                const num = String(x);
                if (isValid(level, num)) {
                    board[i][j] = num;
                    recursion(level + 1);
                    if (level === n * n - 1) {
                        isSolved = true;
                    }
                    // Since unique single soln is promised
                    if (!isSolved) {
                        board[i][j] = '.'; // restore
                    }
                }
            }
        } else {
            if (level === n * n - 1) {
                isSolved = true;
            }
            // Move to next
            recursion(level + 1);
        }
    }
    return recursion(0);
};

Time complexity: O(n^(n*n))

Use bitmasking to store state for faster check

We can use bits to store row, col, and grid decisions.

ABC Puzzle

D - ABC Puzzle

Meet in the middle

Number of subsets having the sum of elements ≤X

1. For given set [1,2,3] and x=5
2. All possible subsets are {}, {1}, {2}, {3}, {1,2},{2,3},{1,3},{1,2,3} i.e. total subsets are 2^N
3. We need to find out the number of subsets with the sum of elements ≤ X
4. In this case, these subsets are {},{1},{2},{3},{1,2},{1,3}
5. Ans would be 6

A brute force approach would be to generate all the subset sum the each subset element and then count the one that verifies the condition.

We can use bitmasking to generate all the subsets.

const soln = (arr, X) => {
  const n = arr.length;
  const ans = [];
  for (let mask = 0; mask < (1<<n); mask++) {
      let sum =0;
      for (let j=0; j < n; j++) {
        if((mask >> j) & 1) {
          sum+= arr[j];
         }
      }
      ans.push(sum);
  }
  ans.sort((a, b) => a - b);
  return ans;
}

Since the mask loop runs 2^N therefore time complexity of the code would be O(N* 2^N) .

The above brute force code works for N<=20 but doesn’t work beyond that. For example, the above code will not work for N <= 40 .

The idea of meeting in the middle

1. Split set into almost two half sets
2. For each set, generate a subset-sum i.e. each will generate 2^(n/2) subset-sum.
3. Now merge these two as a set product. Take one element from set1 and one element from set2 and add them to create a new set.
4. But the last step to build the final set will still create problems for x<=40 .

One approach is, don’t create the final product set, instead apply rule before creating the product set.

1. We can iterate a set A and do a binary search on X-a on set B
2. This is the whole idea of meeting in middle concept

Following is the code to implement it.

const onSmallSet = (arr, X) => {
  const n = arr.length;
  const ans = [];
  for (let mask = 0; mask < (1<<n); mask++) {
      let sum =0;
      for (let j=0; j < n; j++) {
        if((mask >> j) & 1) {
          sum+= arr[j];
         }
      }
      ans.push(sum);
  }
  ans.sort((a, b) => a - b);
  return ans;
}

const soln = (arr, X) => {
  const n = arr.length;
  const ans = 0;
  const newArray = [];
  // Split into almost half
  for (let i=0; i < n; i++) {
    newArray[i&1].push(arr[i]);
  }
  // Run soln on smaller set
  const sub0 = onSmallSet(newArray[0], X);
  const sub1 = onSmallSet(newArray[1], X);
  for (const sum of sub0) {
      ans += binarySearch(sub1, X - sum);
  }
  return ans;
}

Time complexity: O(n* 2^(n/2))

4 SUM: Variant 1

https://leetcode.com/problems/4sum/description/

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Approach

1. Since order doesn’t matter therefore we can sort the input and apply two sum as base with help of left and right pointer.
2. Apply decrease and conquer i.e. for K levle target sum, choose number for kth and launch next recursion to solve the rest by excluding the numbers scanned so far.

Following is the code to implement it.

// Find a & b for given target on sorted array
const twoLevelSum = (nums, target, index) => {
    const n = nums.length;
    const results = [];
    // Apply two pointers
    let left = index;
    let right = n - 1;
    while (left < right) {
        const a = nums[left];
        const b = nums[right];
        // if found target then capture result
        if (a + b == target) {
            results.push([a, b]);
            left++;
            right--;
        }
        // if less than target then move left
        else if (a + b < target) {
            left++;
        } else {
            right--;
        }
        // Handle duplicates
        if (left != index && nums[left] == nums[left - 1]) {
            left++;
            continue;
        }
        if (right != n - 1 && nums[right] == nums[right + 1]) {
            right--;
            continue;
        }
    }
    return results;
}
const kLevelSum = (nums, target, index, k) => {
    const n = nums.length;

    // Base case for two level sum
    if (k == 2) {
        return twoLevelSum(nums, target, index);
    }
    // Apply decrease and counter, i.e. solve for level k and ask worker to solve for k-1 level
    const results = [];
    for (let i = index; i < n; i++) {
        // Handle duplicates
        if (i != index && nums[i] == nums[i - 1]) {
            continue;
        }
        const a = nums[i];
        const remaining = target - a;
        const output = kLevelSum(nums, remaining, i + 1, k - 1);
        // As a manager, take output from worker and solve it
        output.forEach(result => {
            results.push([a, ...result]);
        })
    }
    return results;
}
const usingDecreaseAndCounquer = (nums, target) => {
    // Sort array
    nums.sort((a, b) => a - b);
    return kLevelSum(nums, target, 0, 4);
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    return usingDecreaseAndCounquer(nums, target);
};

4 SUM: Variant 2

Same as above problem but now apply order on a<b<c<d .

Combine rods

String reversal

This post is based on a recursion lecture available at https://maang.in/. The teacher is great, so feel free to buy this course, cost is much less compare to the quality:-)