leetcode546_leetcode 5

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Description

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

Example

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Analyse

对给定的数列做个全排列，貌似这道题没有检查顺序，这时候就能偷个懒，用我们在031写的Next Permutation直接写就好了。

Code

class Solution { 
   
public:
    vector<vector<int>> permute(vector<int>& nums) { 
   
        vector<vector<int>> ans;
        vector<int> origin = nums;
        ans.push_back(origin);
        nextPermutation(nums);
        while (origin != nums) { 
   
            ans.push_back(nums);
            nextPermutation(nums);
        }
        return ans;
    }
    void nextPermutation(vector<int>& nums) { 
   
        if (nums.size() == 0) return;
        int i = nums.size() - 2, j;
        while(i >= 0 && nums[i] >=n ums[i+1]) i--;
        if(i >= 0) { 
     
            j = i + 1;  
            while(j <n ums.size() && nums[j] > nums[i]) j++;  
            j--;
            swap(nums[i], nums[j]);
        }
		i++; j = nums.size() - 1;
		while (i < j) { 
   
			swap(nums[i], nums[j]);
			i++; j--;
		}
	}
};