【題目描述】

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：申請域名、網(wǎng)頁空間、營銷軟件、網(wǎng)站建設(shè)、耿馬網(wǎng)站維護、網(wǎng)站推廣。

Given a list of numbers, return all possible permutations.

Notice:You can assume that there is no duplicate numbers in the list.

給定一個數(shù)字列表，返回其所有可能的排列。

注意:你可以假設(shè)沒有重復(fù)數(shù)字。

【題目鏈接】

http://www.lintcode.com/en/problem/permutations/

【題目解析】

遇到這種問題，很顯然，第一個想法我們首先回去想到DFS,遞歸求解，對于數(shù)組中的每一個元素，找到以他為首節(jié)點的Permutations,這就要求在遞歸中，每次都要從數(shù)組的第一個元素開始遍歷，這樣，，就引入了另外一個問題，我們會對于同一元素訪問多次，這就不是我們想要的答案了，所以我們引入了一個bool類型的數(shù)組，用來記錄哪個元素被遍歷了(通過下標(biāo)找出對應(yīng)).在對于每一個Permutation進行求解中，如果訪問了這個元素,我們將它對應(yīng)下表的bool數(shù)組中的值置為true,訪問結(jié)束后，我們再置為false.

時間復(fù)雜度分析: 這道題同Combination,所以對于這道題的解答，時間復(fù)雜度同樣是

O(n!)

【答案鏈接】

https://www.jiuzhang.com/solutions/permutations/

當(dāng)前題目：Lintcode15Permutationssolution題解-創(chuàng)新互聯(lián)
文章分享：http://www.weahome.cn/article/ddecoe.html