Array Permutation

Array Permutation(数组的全排列)

题目描述：

给定一个数字n，和一个关于需要生成排列的长度k。要求根据这两个数字，从[1…n]的数组中生成长度为k的排列。

例子：

例如给定数字为n=4，k=2；则根据要求生成的排列为[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。

解题思路：

这道题理解上问题不大，主要是在于用什么方法去解决。我们首先想到的是使用回溯的方法来解决。首先是使用一个标签变量来记录我们当前要确定排列中的第几个位置，然后递归的调用函数来确定下面位置的数字。主要的思路体现在代码中，可以看代码中的注释来理解。

代码如下：

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        //保存当前的遍历结果
        vector<vector<int>> res;
        //保存结果
        helper(res, path, n, k);
        //调用函数
        return res;
        
    }
    void helper(vector<vector<int>>& res, vector<int>& path, int n, int k){
        if (k == 0){
            res.push_back(path);
            return;
        }
        //如果确定位置已经到了0，将其保存到结果中
        for (int i = n; i > 0; i--){
            path.push_back(i);
            //先确定一个数
            helper(res, path, i - 1, k - 1);
            //确定下一个数
            path.pop_back();
            //回溯一步，将刚才的数弹出
        }       
    }
};

解题思路2：

当然这道题也可以使用递归的方法来解决。主要不同的是直接生成一个当前路径数组，然后不断的确定当前位置的数字即可。

代码如下：

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > rslt;
        //保存结果
        vector<int> path(k, 0);
        //保存当前遍历的排列结果
        combine(n, k, rslt, path);
        //调用函数
        return rslt;
    }
private:
    void combine(int n, int k, vector<vector<int> > &rslt, vector<int> &path) {
        if (k == 0) {
            rslt.push_back(path);
            return;
        }
        //从排列的尾部开始确定这个位置需要填入什么数字
        //当达到第0个位置的时候将其保存入结果
        for (int i = n; i >= 1; i--) {
            path[k - 1] = i;
            //确定第k个位置的数，从n到1中挑选
            combine(i - 1, k - 1, rslt, path);
        }
    }
};