Leetcode:46. Permutations

Description

Given a collection of distinct numbers, return all possible permutations.

Example

For example,
[1,2,3] have the following permutations:

[
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
]

思路

• 自己寫了一個getNextPermute函數
• STL裡面有一個next_permutation函數

代碼

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int len = nums.size();
        if(len == 0) return res;
        if(len == 1) {
            res.push_back(nums);
            return res;
        }
        
        sort(nums.begin(), nums.end());
        
        do{
            res.push_back(nums);
        }
        while(getNextPermute(nums, len));
        
        return res;    
    }
    
    bool getNextPermute(vector<int>& nums, int len){
        int index1 = 0, index2 = -1, flag = nums[0];
        for(int i = 1; i < len; ++i){
            if(nums[i] > nums[i - 1]){
                index1 = i - 1;
                index2 = i;
                flag = nums[i] - nums[i - 1];
            }
            else if(nums[i] > nums[index1] && nums[i] - nums[index1] < flag){
                index2 = i;
                flag = nums[i] - nums[index1];
            }
        }
        
        if(index2 == -1) return false;
        
        swap(nums[index1], nums[index2]);
        sort(nums.begin() + index1 + 1, nums.end());
        return true;
    }
};

• next_permutation

  class Solution {
  public:
  vector<vector<int>> permute(vector<int>& nums) {
      vector<vector<int>> res;
      int len = nums.size();
      if(len == 0) return res;
      if(len == 1) {
          res.push_back(nums);
          return res;
      }
  
      sort(nums.begin(), nums.end());
  
      do{
          res.push_back(nums);
      }
      while(next_permutation(nums.begin(), nums.end()));
  
      return res;    
  }
  };