Algorithm: Backtracking, Generic solution to 4 Leetcode problems in Javascript

A very handy dandy algorithm is Backtracking. I have to say it took me a while to wrap my head around it and I am still not 100% comfortable with it. So let's dive in head first together!

How it works

This generic solution does three main things:

1. Make a change
2. Try a solution
3. Literally backtrack or reset and try step 1 & 2 again

If you notice in the steps there is a recursive pattern to it. And yes we use recursion to do backtracking.

Types of Problem

In my understanding whenever you are asked to find all possible combination, permutation, subset etc. you will find Backtrack to be handy. I am pretty sure there are many other cases but this is a good start.

Without further ado let's jump into the code.

1. Subsets

Question: Given a set of distinct integers, nums, return all possible subsets (the power set).

var subsets = function(nums) {
    // initialize output array
	let output = [];
    // call backtrack function with base values
    backtrack(output, nums, [], 0); 
    return output;
}

var backtrack = function(output, nums, currentList, start) {
    // pushing currentList to output
	output.push([...currentList]);
    for(let i = start; i < nums.length; i++) {
        // pushing current element to currentList
    	currentList.push(nums[i]);
        // call recursively with the next element in the list
        backtrack(output, nums, currentList, i+1);
        // remove the last pushed element
        currentList.pop();
    }
}

2. Subset 2:

Question: Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

var subsetWithDup = function(nums) {
    // initialize output array
    let output = [];
    // sorrt the list because it contains duplicates
    nums = nums.sort((a, b) => a-b);
    // call backtrack function with base values
    backtrack(output, nums, [], 0);
}

var backtrack = function(nums, output, currentList, start) {
    // pushing currentList to output
    output.push(...[currentList]);
    for(let i = start; i <nums.length; i++) {
        // check to see if adjacent elements are duplicate and just           continue to next one
    	if(i > start && nums[i] === nums[i-1]) continue;
        // pushing current element to currentList
        currentList.push(nums[i]);
        // call recursively with the next element in the list
        backtrack(output, nums, currentList, i+1);
        // remove the last pushed element
        currentList.pop();

        
    }

}

3. Combination Sum

Question: Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

var combinationSum = function(nums, target) {
	let output = [];
    backtrack(nums, output, [], target, 0);
    return output;
}

var backtrack = function(nums, output, currentList, [], remainder, start) {
	if(remainder < 0) return;
    else if(remainder === 0) output.push([...currentList]);
    else {
    	for(let i = start; i < nums.length; i++) {
        	currentList.push(nums[i]);
            backtrack(output, currentList, nums, remainder-nums[i], i);
            currentList.pop();
        }
    }
}

4. Combination Sum 2:

Question: Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

var combinationSum2 = function(nums, target) {
	let output = [];
    backtrack(nums, output, [], target, 0);
}

var backtrack = function(nums, output, currentList, remainder, start) {
    if(remainder < 0) return;
    else if(remainder === 0) output.push([...currentList]);
    else {
        for(let i = start; i < nums.length; i++) {
        	if(i > start && nums[i] === nums[i-1]) continue;
            currentList.push(nums[i]);
            backtrack(nums, output, currentList, remainder-nums[i], i+1);
           currentList.pop();
         }
    	
    }

Hopefully this helped you as much as it helped me! Happy Coding :)