本文共 1858 字，大约阅读时间需要 6 分钟。
递归实现：
class Solution {public: /** * @param nums: A list of integers. * @return: A list of permutations. */ vector > permute(vector nums) { // write your code here vector > permutations; if (nums.empty()) return permutations; permutate(nums, 0, permutations); return permutations; }private: void permutate(vector nums, int start, vector >& permutations) { if (start == nums.size()) { permutations.push_back(nums); return; } for (int i = start; i < (int)nums.size(); i++) { swap(nums[start], nums[i]); permutate(nums, start + 1, permutations); } }}; 非递归实现（基于nextPermutation）：
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers. 5 * @return: A list of permutations. 6 */ 7 vector > permute(vector nums) { 8 // write your code here 9 vector > permutations;10 if (nums.empty()) return permutations;11 vector copy(nums.begin(), nums.end());12 nextPermutation(nums);13 permutations.push_back(nums);14 while (nums != copy) {15 nextPermutation(nums);16 permutations.push_back(nums);17 }18 return permutations;19 }20 private:21 void nextPermutation(vector & nums) {22 int k = -1, n = nums.size();23 for (int i = n - 2; i >= 0; i--) {24 if (nums[i] < nums[i + 1]) {25 k = i;26 break;27 }28 }29 if (k == -1) {30 reverse(nums.begin(), nums.end());31 return;32 }33 int l;34 for (int i = n - 1; i > k; i--) {35 if (nums[i] > nums[k]) {36 l = i;37 break;38 }39 }40 swap(nums[l], nums[k]);41 reverse(nums.begin() + k + 1, nums.end());42 }43 };
转载地址：http://hibnm.baihongyu.com/