c语言backtrack算法6,一个关于数组回溯算法(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

// 停止条件

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都不会进行

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