CY-Left

CPPLeetCode基本功底开发语言

46. permutations 全排列 cpp c++

46. permutations 全排列

原文&翻译

Given a collection of distinct integers, return all possible permutations.
给出不重复的整数集合, 返回所有可能的排列组合

示例

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

结题

  1. 递归
    O(n!)
    全排列, 首先把所有可能放在首位的数字拿出来, 1234, 2134, 3124, 4123,
    然后把后三位拿去递归, 同样把可能放在首位的拿出来, 后两位拿去递归交换, 返回结果即可.
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector <int>> res;
        if(nums.size()==1) {
            res.push_back(nums);
            return res;
        } else {
            recursion(0, nums, res);
        }
        return res;
    }

    int recursion(int pos, vector<int> arr, vector<vector<int>> &rest){
        if(pos == arr.size()-1) { // 抵达末尾
            rest.push_back(arr);
            return 0;
        }
        for(int i=pos; i<arr.size(); i++) {
            int temp = -1;
            temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            recursion(pos+1, arr, rest);
        }
        return 0;
    }
};

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=924