子集与排列问题

子集问题如何回溯求解？

• 决策: 每个元素只有"选"与"不选"两个分支;
• 去重: 下一层从 i + 1 开始遍历, 保证元素下标严格递增, 不产生重复子集;
• 收集时机: 进入函数时先记录当前路径, 因为每个中间状态本身就是一个子集;

const subsets = (nums) => {
  const res = [];
  const backtrack = (state, index) => {
    res.push([...state]);
    for (let i = index; i < nums.length; i++) {
      state.push(nums[i]);
      backtrack(state, i + 1);
      state.pop();
    }
  };
  backtrack([], 0);
  return res;
};

• 复杂度: 时间 $O(n \cdot 2^n)$, 空间 $O(n)$;

全排列问题如何回溯求解？

• 决策: 每个位置从所有未使用的元素中挑一个;
• 状态: 布尔数组 selected 标记元素是否已被放入路径;
• 剪枝: 跳过 selected[i] 为真的元素;
• 收集时机: 路径长度等于元素个数时才记录, 与子集问题不同;

const permute = (nums) => {
  const res = [];
  const selected = new Array(nums.length).fill(false);
  const backtrack = (state) => {
    if (state.length === nums.length) {
      res.push([...state]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (selected[i]) continue;
      selected[i] = true;
      state.push(nums[i]);
      backtrack(state);
      state.pop();
      selected[i] = false;
    }
  };
  backtrack([]);
  return res;
};

• 复杂度: 时间 $O(n \cdot n!)$, 空间 $O(n)$;

含重复元素的全排列如何避免重复？

• 前提: 先排序, 让相同元素相邻;
• 剪枝条件: i >= 1 && nums[i] === nums[i - 1] && !selected[i - 1];
• 含义: 相邻两个相同元素只允许"靠前那个先用", 从而排除 AB 与 BA 这类同一条路径上的重复;
• 注意: 判断依据是 !selected[i - 1] 而非 selected[i - 1], 两者对称, 任选其一即可;

const permuteUnique = (nums) => {
  nums.sort((a, b) => a - b);
  const res = [];
  const selected = new Array(nums.length).fill(false);
  const backtrack = (state) => {
    if (state.length === nums.length) {
      res.push([...state]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (i >= 1 && nums[i] === nums[i - 1] && !selected[i - 1]) continue;
      if (selected[i]) continue;
      selected[i] = true;
      state.push(nums[i]);
      backtrack(state);
      state.pop();
      selected[i] = false;
    }
  };
  backtrack([]);
  return res;
};

• 复杂度: 时间 $O(n \cdot n!)$, 空间 $O(n)$;

子集与全排列的剪枝方式有何区别？

维度	子集	全排列
下一层起点	i + 1	0
去重状态	下标递增即可	selected 数组
记录时机	每个节点	仅叶子节点
结果规模	$2^n$	$n!$

• 原因: 子集不关心顺序, 靠下标递增天然去重; 排列关心顺序, 必须显式记录已用元素;