求集合单词组合起来的不同结果，集合中的单词不重复，每个结果包含所有单词

[Pcjmy]

No description provided.

[veneno-o]

const arr = ["a","b","c","d","e"];

// 回溯算法
function main(arr){
    if(arr.length === 1) return [arr[0]];
    let res = [];
    for(let i = 0; i < arr.length; ++i){
        const newArray = [...arr.slice(0, i),...arr.slice(i + 1)];
        res = res.concat(main(newArray).map(item => arr[i] + item));
    }
    return res;
}
// 5! = 120,正解
console.log(new Set(main(arr)).size)

[tyust512]

/**
 * Generates all possible permutations of the given array.
 * 找好截止条件
 * 都可以抽象为树的深度遍历，只是遍历的过程中要剪枝
 *
 * @param {number[]} nums - The array of numbers to permute.
 * @return {number[][]} - An array containing all possible permutations of the input array.
 */
var permute = function(nums) {
  const res = [];
  const dfs = (numList, temp) => {
    if(temp.length === nums.length) {
      res.push(temp.slice()); // temp是引用类型
      return;
    }

    for(let value of numList) {
      if (temp.includes(value)) continue; // 确保元素不重复
      temp.push(value);
      dfs(numList, temp);
      temp.pop();
    }
  }

  dfs(nums, [])

  return res;
};

const arr = ["a","b","c","d","e"];
console.log(permute(arr))

[Aurora-GSW]

非递归方法

function main(arr) {
    if (!arr.length) return []
    let res = [arr[0]]
    for (let i = 1; i < arr.length; i++) {
        let temp = []
        for (const item of res) {
            for (let x = 0; x <= item.length; x++) {
                temp.push(item.slice(0, x) + arr[i] + item.slice(x))
            }
        }
        res = temp
    }
    return res
}

[dizao006]

回溯算法
// 求集合单词组合起来的不同结果，集合中的单词不重复，每个结果包含所有单词
function permute2(arr) {
  let path = [];
  let restult = [];
  function DFS(index) {
    if (path.length === arr.length) {
      restult.push([...path]);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      if (path.includes(arr[i])) {
        continue;
      }
      path.push(arr[i]);
      DFS(index + 1);
      path.pop();
    }
  }
  DFS(0);
  console.log(restult);
}

permute2(["a", "b", "c", "d", "e"]);