两种思路！

思路 1

  • 单看每个元素，都有两种选择：选入子集，或不选入子集。
  • 比如[1,2,3]，先看1，选1或不选1，都会再看2，选2或不选2，以此类推。
  • 即，考察当前枚举的数，基于选它而继续，是一个递归分支；基于不选它而继续，又是一个分支。
    image.png
  • 用索引index代表当前递归考察的数字A[index]。
  • 当index越界时，说明所有数字考察完了，得到一个解，把它加入解集，结束当前递归分支。

为什么要回溯？

  • 因为不是找到一个子集就完事。
  • 找到一个子集，结束递归，要撤销当前的选择，回到选择前的状态，做另一个选择——不选当前的数，基于不选，往下递归，继续生成子集。
  • 回退到上一步，才能在包含解的空间树中把路走全，回溯出所有的解。
    image.png

代码 javascript

const subsets = (A) => {
  const res = [];

  const dfs = (index, list) => {
    if (index == A.length) { // 指针越界
      res.push(list.slice());   // 加入解集
      return;                   // 结束当前的递归
    }
    list.push(A[index]); // 选择这个数
    dfs(index + 1, list);   // 基于该选择，继续往下递归，考察下一个数
    list.pop();             // 上面的递归结束，撤销该选择
    dfs(index + 1, list);   // 不选这个数，继续往下递归，考察下一个数
  };

  dfs(0, []);
  return res;
};

另一种思路

  • 刚才的思路是：逐个考察数字，每个数都选或不选。等到递归结束时，把集合加入解集。
  • 换一种思路：在执行子递归之前，加入解集，即，在递归压栈前 “做事情”。
    image.png
  • 用 for 枚举出当前可选的数，比如选第一个数时：1、2、3 可选。
    • 如果第一个数选 1，选第二个数，2、3 可选；
    • 如果第一个数选 2，选第二个数，只有 3 可选（不能选1，产生重复组合）
    • 如果第一个数选 3，没有第二个数可选
  • 每次传入子递归的 index 是：当前你选的数的索引+1。
  • 每次递归枚举的选项变少，一直递归到没有可选的数字，那就进入不了for循环，落入不了递归，整个DFS结束。
  • 可见我们没有显式地设置递归的出口，而是通过控制循环的起点，使得最后递归自然结束。

代码 js

const subsets = (A) => {
  const res = [];

  const dfs = (index, list) => {
    res.push(list.slice());     // 调用子递归前，加入解集
    for (let i = index; i < A.length; i++) { // 枚举出所有可选的数
      list.push(A[i]);       // 选这个数
      dfs(i + 1, list);         // 基于选这个数，继续递归，传入的是i+1，不是index+1
      list.pop();               // 撤销选这个数
    }
  };
  dfs(0, []);
  return res;
};