## Monday, November 17, 2014

### [LeetCode] Permutations I, II

Permutations I

Given a collection of numbers, return all possible permutations.
For example,
`[1,2,3]` have the following permutations:
`[1,2,3]``[1,3,2]``[2,1,3]``[2,3,1]``[3,1,2]`, and `[3,2,1]`.

Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
`[1,1,2]` have the following unique permutations:
`[1,1,2]``[1,2,1]`, and `[2,1,1]`.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21``` ```class Solution { public: vector > permute(vector &num) { vector> allPer; if(num.empty()) return allPer; allPer.push_back(vector(1,num[0])); for(int i=1; i per = allPer[j]; per.insert(per.begin()+k, num[i]); allPer.push_back(per); } allPer[j].push_back(num[i]); } } return allPer; } }; ```

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```class Solution { public: vector > permute(vector &num) { vector> allPer; if(num.empty()) return allPer; vector used(num.size(), false); vector per; findPermutations(num, used, per, allPer); return allPer; } void findPermutations(vector &num, vector &used, vector &per, vector> &allPer) { if(per.size()==num.size()) { allPer.push_back(per); return; } for(int i=0; i

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29``` ```class Solution { public: vector > permuteUnique(vector &num) { vector> allPer; if(num.empty()) return allPer; sort(num.begin(),num.end()); vector per; vector used(num.size(),false); findPerUniq(num, used, per, allPer); return allPer; } void findPerUniq(vector &num, vector &used, vector &per, vector> &allPer) { if(per.size()==num.size()) { allPer.push_back(per); return; } for(int i=0; i0 && num[i]==num[i-1] && !used[i-1]) continue; used[i] = true; per.push_back(num[i]); findPerUniq(num, used, per, allPer); per.pop_back(); used[i] = false; } } }; ```