一、[46]全排列

給定一個 沒有重復 數(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ù)組，其實就是記錄此時path里都有哪些元素使用了，一個排列里一個元素只能使用一次

相當于在每個分支上標記使用了那些元素，每個分支，元素只可以使用一次

二、[47]全排列2

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

示例 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、去重一定要對元素進行排序，這樣我們才方便通過相鄰的節(jié)點來判斷是否重復使用了。

2、樹枝去重（更好理解）

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

3、樹層去重（效率更高）

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

回溯總結：一般來說：組合問題和排列問題是在樹形結構的葉子節(jié)點上收集結果，而子集問題就是取樹上所有節(jié)點的結果。

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