递归和回溯

  • 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
  • 因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
  • 如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。
  • 因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

如何思考递归和回溯？

  • 递归过程需要传入原来的数组，通过额外的变量判断应该从数组的哪个位置开始处理。如used[i] = true;和ansArray.push(item);
  • 回溯过程需要将进入递归时的额外设置还原，这样变回父问题的情况才能进入其他子问题分支。如used[i] = false;和ansArray.pop();

如何思考结束条件？

当收集元素的数组ansArray达到原数组长度时，说明收集该数组的一个排列完成，递归结束。

/**
 * 
 * @param num int整型一维数组 
 * @return int整型二维数组
 */
function permute( num ) {
    const ret = []
    const used = Array.from(num, (item) => item = false);  // 用于判断数组中的元素是否使用过，如果使用过则跳过当前元素
    // write code here
    function dfs(num, ansArray=[]) {
        if (ansArray.length === num.length) {
            ret.push(ansArray.slice());
            return;
        }
        for (let i = 0; i < num.length; ++i) {
            if (used[i]) {
                continue;
            }
            
            ansArray.push(num[i]);
            used[i] = true;
            dfs(num, ansArray);
            used[i] = false;
            ansArray.pop();
        }
    } 

    dfs(num, []);

    return ret;
}
module.exports = {
    permute : permute
};