今天在LeetCode看到一篇非常有價值的討論，列舉了一系列列數(shù)組的回溯算法的通用模式，自己動手一個個完成后，感覺對理解回溯算法的原理有很大幫助。

其實(shí)回溯就是按順序的一種窮舉，但是它會設(shè)定停止條件和達(dá)成條件

一旦符合停止條件，直接整體跳過，包括它后面的子集全部跳過

一旦符合達(dá)成條件，便是所需要的數(shù)據(jù)，添加到結(jié)果集合里

一個簡單的例子：

列舉數(shù)組arr的所有的長度相同的組合，字符不重復(fù)

例如：[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){

// 達(dá)成條件

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()

}

}

}

它的運(yùn)行軌跡：

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 ×

一旦父級達(dá)到停止條件，例如2 2，像后面的子集2 2 1，2 2 2都不會進(jìn)行

當(dāng)通過的停止條件并且符合達(dá)成條件的，就是結(jié)果。

總結(jié)

以上是生活随笔為你收集整理的c语言backtrack算法6,一个关于数组回溯算法(backtrack)的通用模式的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。