[LeetCode] Permutations 全排列
Given a collection of numbers, return all possible permutations. For example,
這道題是求全排列問題，給的輸入數(shù)組沒有重復(fù)項(xiàng)，這跟之前的那道 Combinations 組合項(xiàng) 和類似，解法基本相同，但是不同點(diǎn)在于那道不同的數(shù)字順序只算一種，是一道典型的組合題，而此題是求全排列問題，還是用遞歸DFS來求解。這里我們需要用到一個visited數(shù)組來標(biāo)記某個數(shù)字是否訪問過，然后在DFS遞歸函數(shù)從的循環(huán)應(yīng)從頭開始，而不是從level開始，這是和 Combinations 組合項(xiàng) 不同的地方，其余思路大體相同，代碼如下： 解法一  class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > res; vector<int> out; vector<int> visited(num.size(), 0); permuteDFS(num, 0, visited, out, res); return res; } void permuteDFS(vector<int> &num, int level, vector<int> &visited, vector<int> &out, vector<vector<int> > &res) { if (level == num.size()) res.push_back(out); else { for (int i = 0; i < num.size(); ++i) { if (visited[i] == 0) { visited[i] = 1; out.push_back(num[i]); permuteDFS(num, level + 1, visited, out, res); out.pop_back(); visited[i] = 0; } } } } };
還有一種遞歸的寫法，更簡單一些，這里是每次交換num里面的兩個數(shù)字，經(jīng)過遞歸可以生成所有的排列情況，代碼如下： 解法二 class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > res; permuteDFS(num, 0, res); return res; } void permuteDFS(vector<int> &num, int start, vector<vector<int> > &res) { if (start >= num.size()) res.push_back(num); for (int i = start; i < num.size(); ++i) { swap(num[start], num[i]); permuteDFS(num, start + 1, res); swap(num[start], num[i]); } } };
最后再來看一種方法，這種方法是CareerCup書上的方法，也挺不錯的，這道題是思想是這樣的： 當(dāng)n=1時(shí)，數(shù)組中只有一個數(shù)a1，其全排列只有一種，即為a1 當(dāng)n=2時(shí)，數(shù)組中此時(shí)有a1a2，其全排列有兩種，a1a2和a2a1，那么此時(shí)我們考慮和上面那種情況的關(guān)系，我們發(fā)現(xiàn)，其實(shí)就是在a1的前后兩個位置分別加入了a2 當(dāng)n=3時(shí)，數(shù)組中有a1a2a3，此時(shí)全排列有六種，分別為a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根據(jù)上面的結(jié)論，實(shí)際上是在a1a2和a2a1的基礎(chǔ)上在不同的位置上加入a3而得到的。 _ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3 _ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3
解法三: class Solution { public: vector<vector<int> > permute(vector<int> &num) { if (num.empty()) return vector<vector<int> >(1, vector<int>()); vector<vector<int> > res; int first = num[0]; num.erase(num.begin()); vector<vector<int> > words = permute(num); for (auto &a : words) { for (int i = 0; i <= a.size(); ++i) { a.insert(a.begin() + i, first); res.push_back(a); a.erase(a.begin() + i); } } return res; } };
類似題目：
|
|
|
