算法实战：用回溯算法计算商品所有的SKU！

回溯算法：本质上是一种深度优先搜索算法，类似枚举的搜索尝试过程，当发现不满足条件时，就回到上一步，尝试其他解法

回溯法，一般可以解决如下几种问题：

排列问题：N个数按一定规则全排列，有几种排列方式
子集问题：集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

算法框架

function backTrack (选择列表,路径) {
   if (满足结束条件) {
       得到结果
   }
   for i in 列表 {
      if (满足剪支条件) {
         continue;
      }
      选择列表加入路径
      backtrack(选择列表,路径)
      撤销选择
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

现有商品规格如下：

我们将上图抽象为树形结构，用代码表示如下：

const data = [{
  "value": "颜色",
    "list": [
      { "value": "红" },
      { "value": "白" }
    ]}, {
    "value": "大小",
    "list": [
      { "value": "s" },
      { "value": "m" }
    ]}
  ]
1
2
3
4
5
6
7
8
9
10
11
12

用回溯算法生成SKU的所有组合

  function getSKU (specList) {
    const len = specList.length
    if (len === 0) return []
    const result = [];
    const temp = {}
    function backTrack (index) {
      if(index >= len) {
        result.push({...temp}) // 每项规格遍历完成后，就把组合的结果（temp）存到result数组
        return // 返回到上一层
      }
      const { value: specName, list: attrList } = specList[index];
      for (const attr of attrList) { // 遍历当前规格的每项属性
        temp[specName] = attr.value; // 按照{'规格名称': '属性值'}存放到temp对象
        backTrack(index + 1); // 遍历下一项规格，获取下一项规格的属性值
      }
    }
    backTrack(0);
    return result;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

得到结果：

  [ 
    { "颜色": "红", "大小": "s" },
    { "颜色": "红", "大小": "m" },
    { "颜色": "白", "大小": "s" },
    { "颜色": "白", "大小": "m" }
  ]
1
2
3
4
5
6