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:
- Make a change
- Try a solution
- 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 :)