一、[46]全排列

給定一個(gè) 沒(méi)有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。

示例:

• 輸入: [1,2,3]
• 輸出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

其中，不需要使用startIndex

used數(shù)組，其實(shí)就是記錄此時(shí)path里都有哪些元素使用了，一個(gè)排列里一個(gè)元素只能使用一次

相當(dāng)于在每個(gè)分支上標(biāo)記使用了那些元素，每個(gè)分支，元素只可以使用一次

二、[47]全排列2

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ，按任意順序 返回所有不重復(fù)的全排列。

示例 1：

• 輸入：nums = [1,1,2]
• 輸出： [[1,1,2], [1,2,1], [2,1,1]]

示例 2：

• 輸入：nums = [1,2,3]
• 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

1、去重一定要對(duì)元素進(jìn)行排序，這樣我們才方便通過(guò)相鄰的節(jié)點(diǎn)來(lái)判斷是否重復(fù)使用了。

2、樹(shù)枝去重（更好理解）

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {continue;
}

3、樹(shù)層去重（效率更高）

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}

回溯總結(jié)：一般來(lái)說(shuō)：組合問(wèn)題和排列問(wèn)題是在樹(shù)形結(jié)構(gòu)的葉子節(jié)點(diǎn)上收集結(jié)果，而子集問(wèn)題就是取樹(shù)上所有節(jié)點(diǎn)的結(jié)果。

引自：代碼隨想錄 (programmercarl.com)