題目
給定一個(gè)沒有重復(fù)數(shù)字的序列，返回其所有可能的全排列。
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解析
“全排列”就是一個(gè)非常經(jīng)典的“回溯”算法的應(yīng)用。我們知道函似，N 個(gè)數(shù)字的全排列一共有 N! 這么多個(gè)俊庇。
大家可以嘗試一下在紙上寫 3 個(gè)數(shù)字、4 個(gè)數(shù)字魏割、5 個(gè)數(shù)字的全排列，相信不難找到這樣的方法钢颂。
以數(shù)組 [1, 2, 3] 的全排列為例见妒。
我們先寫以 1 開頭的全排列，它們是：[1, 2, 3], [1, 3, 2]甸陌；
再寫以 2 開頭的全排列须揣，它們是：[2, 1, 3], [2, 3, 1]；
最后寫以 3 開頭的全排列钱豁，它們是：[3, 1, 2], [3, 2, 1]耻卡。
我們只需要按順序枚舉每一位可能出現(xiàn)的情況，已經(jīng)選擇的數(shù)字在接下來要確定的數(shù)字中不能出現(xiàn)牲尺。按照這種策略選取就能夠做到不重不漏卵酪，把可能的全排列都枚舉出來幌蚊。
在枚舉第一位的時(shí)候，有 3 種情況溃卡。
在枚舉第二位的時(shí)候溢豆，前面已經(jīng)出現(xiàn)過的數(shù)字就不能再被選取了；
在枚舉第三位的時(shí)候瘸羡，前面 2 個(gè)已經(jīng)選擇過的數(shù)字就不能再被選取了漩仙。
這樣的思路，我們可以用一個(gè)樹形結(jié)構(gòu)表示犹赖《铀看到這里的朋友，建議自己先嘗試畫一下“全排列”問題的樹形結(jié)構(gòu)峻村。
使用編程的方法得到全排列麸折，就是在這樣的一個(gè)樹形結(jié)構(gòu)中進(jìn)行編程，具體來說粘昨，就是執(zhí)行一次深度優(yōu)先遍歷垢啼，從樹的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)形成的路徑就是一個(gè)全排列。
樹形結(jié)構(gòu)圖
代碼
public IList<IList<int>> Permute(int[] nums) {
IList<IList<int>> res = new List<IList<int>>();
int[] tempArr = new int[nums.Length];
bool[] vis = new bool[nums.Length];
BackTrackPermute(0,nums.Length,nums,vis,res,tempArr);
return res;
}
void BackTrackPermute(int cur,int len,int[] nums, bool[] vis,IList<IList<int>> res,int[] tempArr)
{
if (cur == len)
{
res.Add(new List<int>(tempArr));
return;
}
for (int i = 0; i < len; i++)
{
if(vis[i]) continue;//如果已經(jīng)使用則繼續(xù)
vis[i] = true;
tempArr[cur] = nums[i];//把當(dāng)前的cur的值賦為nums[i]的值
BackTrackPermute(cur+1,len,nums,vis,res,tempArr);//繼續(xù)
vis[i] = false; //狀態(tài)重置
}
}
