【leetcode】 46 Permutations

发表于 | 分类于 ，

全排列


描述

求全排列

样例

样例1

1
2
3
4
5
6
7
8
9
输入: [1,2,3]
输出: [
	    [1,2,3],
	    [1,3,2],
	    [2,1,3],
	    [2,3,1],
	    [3,1,2],
	    [3,2,1]
	 ]

思路

全排列，回溯，用一个数字，返还一个数字

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, vector<int>& tmpVec){
        if (tmpVec.size()==nums.size()){
            ans.push_back(tmpVec);
            return;
        }
        for(auto n: nums){
            if (find(tmpVec.begin(), tmpVec.end(), n)==tmpVec.end()){
                tmpVec.push_back(n);
                backtrack(nums, ans, tmpVec);
                tmpVec.pop_back();
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tmp;
        backtrack(nums, ans, tmp);
        return ans;
    }
};

利用之前的代码
leetcode 31题

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
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        res.push_back(nums);
        int i = 0;
        while(!is_sorted(nums.begin(),nums.end(),std::greater<int>())){
            i++;
            nextPermutation(nums);
            res.push_back(nums);
        }
        cout << "i\t" <<i <<endl;
        return res;

    }

     void nextPermutation(vector<int>& nums) {
         if(nums.size()<=1) {return;}
         if(is_sorted(nums.begin(),nums.end(),std::greater<int>())){
            reverse(nums.begin(),nums.end());
         }
         else{
             rec(nums,1);
         }
     }

     bool rec(vector<int>& nums,int start){
         if(is_sorted(nums.begin()+start,nums.end(),std::greater<int>())){
             sort(nums.begin()+start,nums.end());
             //binary search is faster than o(n)
             int index = upper_bound(nums.begin()+start,nums.end(),nums[start-1]) - nums.begin();
             swap(nums[start-1],nums[index]);
             return true;
          }
         else rec(nums,start+1);
         return false;
      }
};

参考

原题链接