回溯问题

[RubyLouvre]

装载问题

有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中每个集装箱重量为[20, w1, ..wi]， 总重量不会大于c1 + c2。 问是否有一个合理的装载方案， 可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。

例子1
输入
3
50 50
[10, 40, 40]
输出
[[1,2],[3]] //船1装上1，2号集装箱，船2裁上3号集装箱
例子2
输入
3
50 50
[20, 40, 40]
输出：
[] 

解法1， 先对船1求最优解，然后将剩下的集装箱丢给船2。这样也网上最流行的解法，CSDN上到处是这个解法的copy，真是醉了。比如下图，看到cw， bestw就知道是出自这一个思路。

  function load(c1, c2, goods) {
    if (!Object(goods).length) {
        return [[], []];
    }
    goods.sort((a, b) => a - b);
    var total = goods.reduce(function(a, b) {
        return a + b;
    }, 0);
    var end = goods.length,
        boat1Sum = 0,
        boat1Best = 0;
    var currGoodsDistribution = {};
    var bestGoodsDistribution = {};
    function backtrack(start) {
        if (start == end) {
            if (boat1Sum > boat1Best) {
                boat1Sum = boat1Best;
                bestGoodsDistribution = {
                    ...currGoodsDistribution
                };
            }
        } else {
            var el = goods[start];
            total -= el;
            if (boat1Sum + el <= c1) {
                currGoodsDistribution[start] = 1;
                boat1Sum += el;
                backtrack(start + 1);
                currGoodsDistribution[start] = 0;
                boat1Sum -= el;
            }
            if (boat1Sum + el > boat1Best) {
                currGoodsDistribution[start] = 0;
                backtrack(start + 1);
            }
            total += el;
        }
    }
    backtrack(0);
    var boat2Sum = 0;
    for (var i = 0; i < goods.length; i++) {
        if (bestGoodsDistribution[i] == 0) {
            boat2Sum += goods[i];
        }
    }

    var result = [[], []];
    if (boat2Sum > c2) { //如果大于船2的装载量
        return result;
    } else {
        for (var i = 0; i < goods.length; i++) {
            if (bestGoodsDistribution[i] == 0) {
                result[1].push(goods[i]);
            } else {
                result[0].push(goods[i]);
            }
        }
    }
   // console.log(JSON.stringify(result));
    return result;
}
var result = 0;
for (var i = 0; i < 500; i++) {
    var time = new Date();
    load(50, 50, [10, 30, 10, 25, 20]);
    result += new Date() - time;
}
console.log("load1", result / 500);

解法2， 构建解空间树，然后我们在最后一层，从两端起收集可能的解。

function load2(c1, c2, goods) {
    if (!Object(goods).length) {
        return [];
    }
    goods.sort((a, b) => a - b);
    var root = [],
        level = [root],
        newLevel = [];
    for (var i = 0; i < goods.length; i++) {
        for (let j = 0; j < level.length; j++) {
            root = level[j];
            var node = root.concat(goods[i]);
            // root.left = node; //让它更像二叉树
            newLevel.push(node);
            var node = root.concat();
            // root.right = node;//让它更像二叉树
            newLevel.push(node);
        }
        level = newLevel;
        newLevel = [];
    }
    var n = level.length, cn = goods.length, isOk
    for (var i = 0; i < n / 2; i++) {
        var boat1 = level[i];
        var boat2 = level[n - i - 1];
        if (
            boat1.length + boat2.length == cn &&
            sum(boat1) <= c1 &&
            sum(boat2) <= c2
        ) {
            isOk = [boat1, boat2]
            break
        }
    }
    var result = isOk || [[], []]
  //  console.log(JSON.stringify(result));
    return result//返回最后一层
}
var result2 = 0;
for (var i = 0; i < 500; i++) {
    var time = new Date();
    load2(50, 50, [10, 30, 10, 25, 20]);
    result2 += new Date() - time;
}
console.log("load2", result2 / 500);

解法3，这是我从leetcode的摆火柴棍的一个外国解法学到，只不过原题是四条边，需要4个子数组，这里两条船，需要两个子数组。

function load3(c1, c2, goods) {
    if (!Object(goods).length) {
        return false;
    }
    goods.sort();
    var boats = [[], []];
    var curr = [0, 0];
    var max = [c1, c2];
    function backtrack(start) {
        if (start >= goods.length) {
            return curr[0] <= max[0] && curr[1] <= max[1];
        } else {
            var cur = goods[start];
            for (var i = 0; i < 2; i++) {
                if (curr[i] + cur > max[i]) {
                    continue;
                }
                curr[i] = curr[i] + cur;
                boats[i].push(cur);
                if (backtrack(start + 1)) {
                    return true;
                }
                curr[i] = curr[i] - cur;
                boats[i].pop();
            }
        }
        return false;
    }
    backtrack(0);
    // console.log(JSON.stringify(boats));
    return boats;
}

var result3 = 0;
for (var i = 0; i < 500; i++) {
    var time = new Date();
    load3(50, 50, [10, 30, 10, 25, 20]);
    result3 += new Date() - time;
}
console.log("load3", result3 / 500);

[RubyLouvre]

有重复元素的子集问题

var subsetsWithDup = function(nums) {
                if (!Object(nums).length) {
                    return [];
                }
                nums.sort();
                var result = [];
                backtrack(result, [], nums, 0, {});
                return result;
            };

            function backtrack(result, candidate, nums, i, hash) {
                if (i > nums.length) {
                    return;
                }
                if (!hash[candidate]) {
                    //在结果中进行防止重复
                    result.push(candidate.concat()); //没有长度限制
                    hash[candidate] = 1;
                }
                // for (var i = start; i < n; i++) {
                candidate.push(nums[i]); //试探
                backtrack(result, candidate, nums, i + 1, hash);
                candidate.pop(); //不管成功与否，退回上一步
                backtrack(result, candidate, nums, i + 1, hash);
                //  }
            }
            console.log(subsetsWithDup([4, 4, 4, 1, 4]));

[RubyLouvre]

摆火柴棍

function makesquare(nums) {
    if (Object(nums).length < 4) {//如果火柴数量不足4，肯定摆不出正方形
        return false;
    }
    var sides = [[], [], [], []];
    var total = nums.reduce(function(prev, el) {
        return prev + el;
    }, 0);
    if (total % 4) { //如果不能被4整除
        return false;
    }
    nums.sort();
    var max = total / 4,  curr = [0, 0, 0, 0],end = nums.length;
    function backtrack(sides, nums, start, curr, max) {
        if (start >= end) {
            return (
                curr[0] == max &&
                curr[1] == max &&
                curr[2] == max &&
                curr[3] == max
            );
        } else {
            for (var i = 0; i < 4; i++) {
                if (curr[i] + nums[start] > max) {
                    continue;
                }
                sides[i].push(nums[start]); //这个可以不要
                curr[i] += nums[start];
                if (backtrack(sides, nums, start + 1, curr, max)) {
                    return true;
                }
                sides[i].pop(); //这个可以不要
                curr[i] -= nums[start];
            }
        }
        return false;
    }

    var result = backtrack(sides, nums, 0, curr, max);
    console.log(JSON.stringify(sides), result);
    return result;
}

makesquare([4, 3, 3, 2, 2, 1, 1]);

[RubyLouvre]

子集问题的构建空间树法

在网上，回溯算法也会与一种叫解空间树的数据结构联系在一起。因为我们遍历题目给出的元素过程中，会产生许多解，这些解其实是形成一棵树。

以第1题为例，其树结构是这样的：

![image_1dlkmg1a9tvv19di1vru1c16188bm.png-41.2kB][2]

因此我们只要一层层构建这棵空间树，拿到最后一层就是解。

function subsets(nums) {
    if (!Object(nums).length) { 
        return []
    }
    nums.sort()
    var root = [], level = [root], newLevel = []
    for (var i = 0; i < nums.length; i++) {
        for (let j = 0; j < level.length; j++) {
            root = level[j];
            var node = root.concat(nums[i])
            root.left = node; //让它更像二叉树
            newLevel.push(node)
            var node = root.concat()
            root.right = node;//让它更像二叉树
            newLevel.push(node);
        }
        level = newLevel;
        newLevel = [];
    }
    return level; //返回最后一层
};

subsets([1, 2, 3]);
console.log(a)

第2题，因为它的元素存在重复，因此必须结果集中的子数组存在重复，因此我们只要在上面的解法中做一次去重操作就行了。

第3题，有重复元素的子集问题, 由于我们的空间树是每层放入数组的不同元素，因此无法用这构建树的方式解决它。

第4题，无重复元素的子集问题, 可以，但是结果集不是集中在最后一层，而是分布在树的各个位置，并且在构建过程中，我们可以裁剪无效分支。

function combinationSum(nums, target) {
    if (!Object(nums).length) {
        return []
    }
    nums.sort()
    var root = [], level = [root], newLevel = []
    root.sum = 0;
    var result = [], hash = {}
    for (var i = 0; i < nums.length; i++) {
        for (let j = 0; j < level.length; j++) {
            root = level[j];
            var node = root.concat(nums[i])
            var sum = root.sum + nums[i]
            if (sum === target) {
                if (!hash[node]) {//去重
                    hash[node] = 1;
                    result.push(node)
                }
                continue
            }
            if (sum < target) {
                root.left = node; //让它更像二叉树
                node.sum = sum
                newLevel.push(node)
            }
            var node = root.concat()
            root.right = node;   //让它更像二叉树
            node.sum = root.sum;
            newLevel.push(node);
        }
        level = newLevel;
        newLevel = [];
    }
    return level
};

combinationSum([10, 1, 2, 7, 6, 1, 5], 8);

问题5，装载问题，我们的集装箱放了这条船就不能放另一条，说明它们不在同一分支上。又由于我们需要装完所有箱子，因此它们只会出现在最后一层。再仔细观察，每个子集是呈左右对称分布的。因此我们拿到最后一层，然后左右同时取两个元素进行比较就能得出结果

![image_1dlmq8mvbg3gv6ur8ue9u1al81s.png-21.2kB][3]

function sum(arr) {
    return arr.reduce(function(prev, el) {
        return prev + el;
    }, 0);
}

function load(c1, c2, goods) {
    if (!Object(goods).length) {
        return [];
    }
    goods.sort();
    var root = [], level = [root],
    //略掉构建空间树的部分，读者自行补完
    var n = level.length， cn = goods.length;
    for (var i = 0; i < n / 2; i++) {
        var boat1 = level[i];
        var boat2 = level[n - i - 1];
        if (
            boat1.length + boat2.length == cn &&
            sum(boat1) <= c1 && sum(boat2) <= c2
        ) {
            return [boat1, boat2];
        }
    }
    return []; //返回最后一层
}
load(50, 50, [20, 30, 25]);

问题6, 同上，就是子数组多一点而已。

[RubyLouvre]

组合问题

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

注意只要装k个

  function combine(n, k) {
            var result = [], condidate = []
            function backtrack(start) {
                if (condidate.length == k) {
                    result.push(condidate.concat())
                } else {
                    for (var i = start; i <= n; i++) {
                        condidate.push(i)
                        backtrack(i + 1)
                        condidate.pop()
                    }
                }
            }
            backtrack(1);
            return result;
        }
        console.log(combine(4, 2))

[RubyLouvre]

括号问题

function parentheses(n) {
    var leftnum = n, rightnum = n;//左括号和右括号都各有n个
    var result = []
    function backtrack(sublist, leftnum, rightnum) {
        if (leftnum == 0 && rightnum == 0) {//结束
            result.push(sublist);
        }
        if (rightnum > leftnum) {//选择和条件。对于不同的if顺序，输出的结果顺序是不一样的，但是构成一样的解空间
            backtrack(sublist + ")", leftnum, rightnum - 1);
        }
        if (leftnum > 0) {
            backtrack(sublist + "(", leftnum - 1, rightnum);
        }
    }
    backtrack("", leftnum, rightnum);
    console.log(result);
}
parentheses(3)

[RubyLouvre]

有重复元素的子集问题

给定一个可能有重复元素的整数数组nums，返回该数组所有可能的子集（幂集）。注意：结果集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

与上题只有一点差别，但它只是对候选集做出限制，即结果集中不能出现两个[1,2]数组。这个我们可以使用hash去重。

var subsetsWithDup = function (nums) {
    if (!Object(nums).length) {
        return [];
    }
    nums.sort((a, b) => a - b)
    var result = [], candidate = [], end = nums.length, hash = {};
    function backtrack(start) {
        if (!hash[candidate]) { //在结果中进行防止重复
            result.push(candidate.concat());//没有长度限制
            hash[candidate] = 1;
        }
        for (var i = start; i < end; i++) {
            candidate.push(nums[i]) //试探
            backtrack(i + 1);
            candidate.pop(); //不管成功与否，退回上一步
        }
    }
    backtrack(0);
    return result;
};
subsetsWithDup([4, 4, 4, 1, 4])

当然，我们还可以在递归函数的for循环中做去重，感兴趣的同学可以试一下。

[RubyLouvre]

装船问题

 function boatLoad(goods, c1, c2) {
            var allocation = new Array(goods.length).fill(0); //用于表示它分配到哪一条船
            var result = []
            var boatsNum = 0;  //总共有多少条船
            var curLoad = [0]; //索引0没有用
            var maxLoad = [0]; //索引0没有用
            //初始化数据
            for (var i = 1; i < arguments.length; i++) {
                curLoad[i] = 0;
                maxLoad[i] = arguments[i]
                boatsNum++;
            }
            function backtrack(start, isFull) {//start表示集装箱的编号
                if (start >= goods.length) {
                    if (!isFull) {
                        return false
                    }
                    for (let i = 1; i <= boatsNum; i++) {
                        if (curLoad[i] > maxLoad[i] || curLoad[i] > maxLoad[i]) {
                            return false;//不能超过该船的最大装载量
                        }
                    }
                    result = allocation.concat()
                    return true
                } else {
                    for (let i = 1; i <= boatsNum; i++) {
                        allocation[start] = i;  //1装在船1; 2装在船2
                        if (curLoad[i] + goods[start] <= maxLoad[i]) {
                            curLoad[i] += goods[start]
                            if (backtrack(start + 1, i == boatsNum)) {
                                return true
                            }
                            curLoad[i] -= goods[start]
                        }
                    }
                }
            }
            backtrack(0)
            // console.log(allocation, '!!!')
            return allocation
        }
        var result4 = 0;
        for (var i = 0; i < 500; i++) {
            var time = new Date();
            boatLoad([10, 30, 10, 25, 20], 50, 50);
            result4 += new Date() - time;
        }
        console.log("load4", result4 / 500);
        console.log(boatLoad([10, 50, 10, 20, 20, 10], 50, 50, 50))

[RubyLouvre]

批处理作业调度

题目 https://blog.csdn.net/gavinloverqq/article/details/51313458 https://blog.csdn.net/limbos/article/details/50385540#comments

function swap(x, t, j) {
    var temp = x[t];
    x[t] = x[j];
    x[j] = temp;
}

function schedule2() {
    var work = [[0, 0], [2, 1], [3, 1], [2, 3]]
    //可以分段赋值也可以,逐个赋值用,隔开
    var n = 3;
    var best = 1000;
    var order = [0, 1, 2, 3];//排列树的初始化
    var flow = [0, 0, 0, 0]
    var bestFlow = []

    function backTrack(t) {
        if (t > n) {
            var sum = 0;

            for (var i = 1; i <= n; i++) {
                flow[i] = flow[i - 1] + Math.abs(work[order[i]][0] - work[order[i - 1]][1]) + work[order[i]][1];
                sum += flow[i];
            }

            if (sum < best) {
                best = sum;
                bestFlow = order.concat()

            }
        }
        else {
            for (var i = t; i <= n; ++i) {
                swap(order, t, i);
                backTrack(t + 1);
                swap(order, t, i);
            }
        }
    }
    backTrack(1)

    console.log(bestFlow, best)
}

function schedule3(n, time1, time2) {
    var work = []
    for (var i = 0; i < n; i++) {
        work[i] = [time1[i], time2[i]]
    }
    var condidtate = [] //排列树最开始的解为0，1，2
    //机器1,2完成某个作业的结束时间
    var flow1 = [], flow2 = [];
    var best = Infinity, bestFlow = [];
    //我们使用hash实现全排列，否则需要引入两个swap方法
    var hash = {}
    function backTrack(start) {
        if (start == n) {
            for (var i = 0; i < n; i++) {
                var index = condidtate[i];
                flow1[i] = (flow1[i - 1] || 0) + work[index][0]
                flow2[i] = Math.max((flow2[i - 1] || 0) + flow1[i]) + work[index][1]
            }
            var sum = flow2[n - 1]
            if (sum < best) {
                best = sum;
                bestFlow = condidtate.concat()
            }
        } else {
            for (var i = 0; i < n; i++) {
                if (!hash[i]) {
                    condidtate.push(i)
                    hash[i] = 1
                    backTrack(start + 1);
                    condidtate.pop();
                    hash[i] = 0
                }
            }
        }
    }
    backTrack(0)
    console.log("最小完成时间和", best)
    console.log("最佳调度顺序为", bestFlow)
    return [best, bestFlow]
}
schedule3(3, [2, 3, 2], [1, 1, 3])

[RubyLouvre]

独立任务最优调度（双机调度）问题

https://blog.csdn.net/qq_26658823/article/details/78298957

[RubyLouvre]

最佳调度问题

https://blog.csdn.net/Pavcd/article/details/80821353

[RubyLouvre]

01背包问题

function knapsack01(n, weights, values, capacity) {
    var allocation = new Array(n).fill(0); //表示它选中了没有;
    var curValue = 0,
        curWeight = 0,
        maxValue = 0,
        maxWeight = 0,
        result = [];
    function backtrack(start) {//start为物号的编号
        if (start == n) {
            //这只是其中一个候选项
            if (curValue > maxValue) {
                maxValue = curValue;
                maxWeight = curWeight;
                result = allocation.concat();
            }
        } else {
            for (var i = 0; i < 2; i++) {
                if (curWeight + i * weights[start] <= capacity) {
                    allocation[start] = i; //0不装，1装
                    curWeight += i * weights[start];
                    curValue += i * values[start];
                    backtrack(start + 1);
                    curWeight -= i * weights[start];
                    curValue -= i * values[start];
                }
            }
        }
    }
    backtrack(0);
    console.log(maxValue, maxWeight, allocation);
    return [maxValue, allocation];
}
knapsack01(5, [10, 20, 30, 40, 50], [20, 30, 65, 40, 60], 100);

[RubyLouvre]

数独问题

你一定听说过“数独”游戏。 如下图所示，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。 数独的答案都是唯一的，所以，多个解也称为无解。 本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说，恐怕易如反掌了。 本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。 格式要求，输入9行，每行9个数字，0代表未知，其它数字为已知。 输出9行，每行9个数字表示数独的解。 输入：

005300000 800000020 070010500 400005300 010070006 003200080 060500009 004000030 000009700

程序应该输出： 145327698 839654127 672918543 496185372 218473956 753296481 367542819 984761235 521839764

再例如，输入: 800000000 003600000 070090200 050007000 000045700 000100030 001000068 008500010 090000400

程序应该输出:  812753649 943682175 675491283 154237896 369845721 287169534 521974368 438526917 796318452

数独游戏使用深度优先搜索的方法是比较方便的，可以搜出数独的所有合法的解（使用其他的方法来解决是非常困难的或者是不可能的）

function solveSudoku(board) {
    var result = []
    function backtrack(x, y) {
        if (x == 9) {
            board.forEach(function (row) {
                result.push(row.concat())
            })
            return true
        } else {
            if (board[x][y] == '.') {
                for (var i = 1; i <= 9; i++) {
                    if (check(board, x, y, i)) {
                        board[x][y] = i + ""
                        if (backtrack(x + Math.floor((y + 1) / 9), (y + 1) % 9)) {
                            return true
                        }
                    }
                }
                board[x][y] = '.';
            } else {
                if (backtrack(x + Math.floor((y + 1) / 9), (y + 1) % 9)) {
                    return true
                }
            }
        }

    }
    function check(board, x, y, k) {
        for (var i = 0; i < 9; i++) {
            //我们想在board[x][y] 中填入k， 结果在board[x][i] 或 board[i][y] 出现相同的k
            if (board[x][i] == k + '' || board[i][y] == '' + k) {
                return false;
            }
        }
        //检查九宫格
        var xx = Math.floor(x / 3)
        var yy = Math.floor(y / 3)
        for (var i = xx * 3; i < (xx + 1) * 3; i++) {
            for (var j = yy * 3; j < (yy + 1) * 3; j++) {
                if (board[i][j] == '' + k) {
                    return false;
                }
            }
        }
        return true;
    }
    backtrack(0, 0)
    console.log(JSON.stringify(result))
    return result;
}
solveSudoku(
    [["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
)

[RubyLouvre]

    function solveSudoku(board) {
            var result = []
            function backtrack(x, y) {
                if (x == 9) {
                    board.forEach(function (row) {
                        result.push(row.concat())
                    })
                    return true
                } else {

                    if (board[x][y] == '.') {
                        for (var i = 1; i <= 9; i++) {
                            if (check(board, x, y, i + '')) {
                                board[x][y] = i + ""
                                if (backtrack((y == 8 ? x + 1 : x), (y == 8 ? 0 : y + 1))) {
                                    return true
                                }
                            }
                        }
                        board[x][y] = '.';
                    } else {
                        if (backtrack((y == 8 ? x + 1 : x), (y == 8 ? 0 : y + 1))) {
                            return true
                        }
                    }
                }

            }
            function check(board, x, y, k) {
                for (var i = 0; i < 9; i++) {
                    //我们想在board[x][y] 中填入k， 结果在board[x][i] 或 board[i][y] 出现相同的k
                    if (board[x][i] == k || board[i][y] == k) {
                        return false;
                    }
                }
                //检查九宫格
                var xx = Math.floor(x / 3)
                var yy = Math.floor(y / 3)
                for (var i = xx * 3; i < (xx + 1) * 3; i++) {
                    for (var j = yy * 3; j < (yy + 1) * 3; j++) {
                        if (board[i][j] == k) {
                            return false;
                        }
                    }
                }
                return true;
            }
            backtrack(0, 0)
            console.log(JSON.stringify(result))
            return result;
        }

[RubyLouvre]

找字符串

leetcode 212
Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

function findWords(board, words) {
      var visited = new Array(board.length).fill(0).map(function (el, i) {
        return new Array(board[0].length).fill(false)
      })
      var res = []
      var set = new Set();
      for (var word of words) {
        set.add(word);
      }

      function backtrack(cur, x, y) {
        if (x == board.length || x < 0 || y == board[0].length || y < 0 || visited[x][y]) {
          return;
        }

        var c = board[x][y];
        if (set.has(cur + c)) {
          res.push(cur + c);
          set.delete(cur + c);
        }
        visited[x][y] = true;
        backtrack(cur + c, x + 1, y);
        backtrack(cur + c, x - 1, y);
        backtrack(cur + c, x, y + 1);
        backtrack(cur + c, x, y - 1);
        visited[x][y] = false;
      }

      for (var i = 0; i < board.length; i++) {
        for (var j = 0; j < board[0].length; j++) {
          backtrack("", i, j);
        }
      }
      return res;
    }

    var board = [
      ['o', 'a', 'a', 'n'],
      ['e', 't', 'a', 'e'],
      ['i', 'h', 'k', 'r'],
      ['i', 'f', 'l', 'v']
    ],
      words = ["oath", "pea", "eat", "rain"]

    console.log(findWords(board, words))