一个关于数组回溯算法(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 1
,2 2 2
都不会进行
当通过的停止条件
并且符合达成条件
的,就是结果。
相关推荐
hugebawu 2020-10-12
风吹夏天 2020-07-18
莫明天涯 2020-07-05
pengkingli 2020-06-25
ustbfym 2020-06-17
wonner 2020-06-04
SystemArchitect 2020-06-02
dbhllnr 2020-05-15
wonner 2020-04-25
seekerhit 2020-04-20
yedaoxiaodi 2020-04-19
sunjunior 2020-03-08
faiculty 2020-03-03
dushine00 2020-02-18
nurvnurv 2020-02-02
troysps 2020-01-08
rein0 2020-01-01
yishujixiaoxiao 2019-12-30