每日一道算法Day27–令人头疼的回溯

题目描述:

最近几天刷的题基本都是回溯算法, 但是感觉还是有点迷惑, 于是今天再来了两道回溯入门级别的题目。

大致思路:

递归, 然后一路走到黑, 排出掉不符合要求的情况。

第一道: 因为给定的数组无重复数据, 所以限制条件只有当长度与给定数组长度相同即为递归的结束条件。

代码如下:

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  if (nums.length === 0) {
    return [];
  }

//递归函数
  const fn = (path: number[], arr: number[]) => {
  
  //结束条件
    if (arr.length === 0) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < arr.length; ++i) {
      const tmp = [...path, arr[i]];
      fn(tmp, arr.filter((item) => item !== arr[i]));
    }
  };

  fn([], nums);
  return res;
}
复制代码

第二道: 限制条件为需要去重复

代码如下:

 function permuteUnique(nums: number[]): number[][] {
  const res: number[][] = [];
  if (nums.length === 0) {
    return [];
  }
  
  //先按顺序排序, 方便后面去重
  nums.sort((a, b) => a - b);

  const fn = (path: number[], arr: number[]) => {
    if (arr.length === 0) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < arr.length; ++i) {
    //去重条件
      if (arr[i] !== arr[i - 1]) {
        const tmp = [...path, arr[i]];
        fn(tmp, removeArr(arr, arr[i]));
      }
    }
  };

  fn([], nums);
  return res;
}

//移出数组中的一个指定元素
 function removeArr<T>(arr: T[], value: T) {
  let index = arr.findIndex((p) => p === value);
  return arr.filter((_, _index) => index !== _index);
}
复制代码