Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Permutations

Leetcode algorithms 第 46 题:Permutations。

题目

Given a collection of numbers, return all possible permutations.

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

解答

全排列问题。使用递归算法,每次从当前位置x及其后面的位置中选择一个数放到位置x上,然后递归处理后续位置,直到到达末尾为止。这里选择一个数到位置x上时可以通过交换两个数字快速完成,但需要在递归结束进行回溯,因为下一次需要再次选择。

具体代码如下:

class Solution {
public:
    void f(int x, vector<int> &cur, vector<vector<int> > &ans){
        if (x == cur.size()) //到达末尾
        {
            ans.push_back(cur);
            return;
        }
        for (int i = x; i < cur.size(); i++) //从第x个数及其后面选择一个
        {
            swap(cur[x], cur[i]);
            f(x+1, cur, ans);
            swap(cur[x], cur[i]);
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > ans;
        f(0, num, ans);
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论