全排列

依据回溯算法构建，需要预先将数据排序

PS: 求全排列的问题一般规模都不大，所以可以有限考虑使用递归简单实现，如果超时或者栈溢出，可以考虑替换为迭代版本（基于栈数据结果实现）。

递归版本

function permutation(d) {
  let data = [...d].sort((a, b) => a - b);
  let ans = [];
  // 记录哪些元素已经使用过
  let visited = new Array(d.length).fill(false);
  const bk = (t) => {
    if (t.length === d.length) {
      ans.push([...t]);
      return;
    }
    for (let i = 0; i < data.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        t.push(data[i]);
        bk(t);
        t.pop();
        visited[i] = false;
      }
    }
  };
  bk([]);
  return ans;
}

下一个排列

思路：降序序列最大

从后向前寻找满足降序规则d[i] >= d[i+1]的第一个元素i，那么i-1下标比i下标元素要小，i-1就是要调整的目标下标位置，由于向前循环，i--，所以循环退出时，i已经减一。
在(i，len)区间内，从后向前向左寻找第一个d[i] >= d[j]的下标j，但循环跳出后j位置的元素一定大于i-1位置的元素。
交换i和j下标对应的元素。

将i之后的元素反转为升序，满足与目标d的字母序的差距最小。

function next_permutation(d) {
let i = d.length - 2;
while (i >= 0 && d[i] >= d[i+1]){ i--; }
if (i < 0) return false;
let j = d.length - 1;
while (j >= i + 1 && d[i] >= d[j]) { j--; }
swap(d, i, j);
reverse(d, i + 1, d.length - 1);
return true;
}

上一个排列

思路：升序序列最小

从后向前寻找满足升序规则d[i-1] > d[i]的第一个元素i，那么i-1下标比i下标元素要大，i-1这个位置就是要调整的目标。
在[i, len)内向右寻找最后一个d[j]使得d[j] < d[i-1]，这样循环退出时，j-1就是满足条件的下标，与i-1交换，使i-1位置的元素变小。

重排[i, len)内的元素，使后面的元素能够变成降序.

function prev_permutation(d) {
let i = d.length - 1;
while (i > 0 && d[i-1] <= d[i]) {i--;}
if (i <= 0) return false;
let j = i;
while (j < d.length && d[j] < d[i-1]) { j++;}
swap(d, i-1, j-1);
reverse(d, i, d.length - 1);
return true;
}

子集

思路：求排列的时候是所有元素都在是加入结果集，那么子集就是每次都加入结果集，不过要处理集合的重复性

function subsets(d) {
  let data = [...d].sort((a, b) => a - b);
  let ans = [];
  // 记录哪些元素已经使用过
  let visited = new Array(d.length).fill(false);

  // 记录哪些子集已经添加
  let ct = new Set();

  const compute = (masks) => {
    let r = 0;
    for (let i = 0; i < marks.length; i++) {
      r += (1 << masks[i]);
    }
    return r;
  };

  const bk = (t) => {
    if (t.length <= d.length) {
      let c = compute(t);
      if (!ct.has(c)) {
          ans.push([...t]);
        ct.add(c);
      }
    }
    for (let i = 0; i < data.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        t.push(data[i]);
        bk(t);
        t.pop();
        visited[i] = false;
      }
    }
  };

  bk([]);
  return ans;
}

后续优化思路：
1、使用迭代版本；
2、visited和ct都是记录当前使用了的数组下标，可以考虑合并状态，有个注意实现事项是，t中保存的数据可以更换为下标。

permutation（排列）

全排列

递归版本

下一个排列

上一个排列

子集