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

algorithm Apr 1, 2020

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 :)