一个关于数组回溯算法(backtrack)的通用模式

今天在LeetCode看到一篇非常有价值的讨论,列举了一系列列数组的回溯算法的通用模式,自己动手一个个完成后,感觉对理解回溯算法的原理有很大帮助。

原地址

其实回溯就是按顺序的一种穷举,但是它会设定停止条件达成条件

一旦符合停止条件,直接整体跳过,包括它后面的子集全部跳过

一旦符合达成条件,便是所需要的数据,添加到结果集合里

一个简单的例子:

列举数组arr的所有的长度相同的组合,字符不重复
例如:[1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

代码(js):

function subSet(nums){
  let result=[],temp=[]
  backtrack(result,temp,nums)
  return result
  function backtrack(result,temp,nums){
    // 达成条件
    if(temp.length===nums.length)result.push(temp.slice())
    for(let i=0;i<nums.length;i++){
      // 停止条件
      if(temp.includes(nums[i]))continue
      temp.push(nums[i])
      backtrack(result,temp,nums)
      temp.pop()
    }
  }
}

它的运行轨迹:

1
1 1   ×
1 2
1 2 1 ×
1 2 2 ×
1 2 3 √
1 3
1 3 1 ×
1 3 2 √
1 3 3 ×
2
2 1
2 1 1 ×
2 1 2 ×
2 1 3 √
2 2   ×
2 3
2 3 1 √
2 3 2 ×
2 3 3 ×
3
3 1
3 1 1 ×
3 1 2 √
3 1 3 ×
3 2
3 2 1 √
3 2 2 ×
3 2 3 ×
3 3   ×

一旦父级达到停止条件,例如2 2,像后面的子集2 2 12 2 2都不会进行

当通过的停止条件并且符合达成条件的,就是结果。

相关推荐