排列和组合算法

• 排列无重复

function permute(nums) {
    const res = [], path = [];
    const used = new Array(nums.length).fill(false);
    const dfs =()=> {
        if (path.length === 3) { // 递归出口：当path的长度等于length
            res.push(path.slice()); // 把path的一份拷贝加入到最后的结果res中，然后返回
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 如果之前已经出现过了，直接跳过
            path.push(nums[i]);
            used[i] = true; // 表示这个位置已经用过了
            dfs(); // 递归 回溯
            path.pop(); // 回溯的过程中，将当前的节点从 path 中删除
            used[i] = false;
        }
    }
    dfs();
    return res;
}
console.log(permute([1,2,3,4,5]))

• 待排列数据中有重复，需要去重

function permuteUnique(nums) { 
  const ans = []
  const arr = []
  const used= []
  function helper() { 
    if (arr.length === nums.length) {
      ans.push(arr.slice(0))
      return
    }
    let last = undefined  //新增
    for (let i = 0; i < nums.length; i++){
      if (used[i]) continue
      if (last == nums[i]) continue //新增
      last = nums[i]  //新增
      used[i] = true
      arr.push(nums[i])
      helper()
      arr.pop(nums[i])
      used[i]=false
    }
  }
  helper();
  return ans
}

• 组合问题

var combine = function (n, k) {
  let arr = []
  let ans = []
  function helper(index) {
    if (arr.length === k) {
      ans.push(arr.slice(0))
      return
    }
    for (let i = index; i < n; i++) {
      arr.push(i)
      helper(i + 1)
      arr.pop()
    }
  }
  helper(0)
  return ans
};
console.log(combine(5,3))

转自 作者：IAM17 链接：https://juejin.cn/post/7045653676328747022 来源：稀土掘金 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。