C递归版的全排列和组合算法

浏览数：25 / 时间：2015年06月08日

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].

全排列：

从1开始递归，然后对2递归，最后对3递归

顺序是先输出 1 2 3 1 3 2 2 1 3 2 3 1 ............稍微分析一下就出来了

class Solution {
private:
    vector<vector<int>>res;
    vector<int>tmp;
public:
    vector<vector<int> > permute(vector<int> &num) {
        dfs(res,num,0);
        return res;
    }
    
    void dfs(vector<vector<int>>&res,vector<int>&num,int cur)
    {
        int n=num.size();
        if(cur==n)
        {
            res.push_back(num);
            return;
        }
        for(int i=cur;i<n;i++)
        {
            swap(num[cur],num[i]);
            dfs(res,num,cur+1);
            swap(num[cur],num[i]);
        }
    }
};

类似的还有组合算法。这里给的是1.。。n数的K排列

class Solution {

private:

    vector<int>tmp;
    vector<vector<int>>res;

public:
    vector<vector<int> > combine(int n, int k) {
        if(n==0)
            return res;
        tmp.resize(k);
        dfs(0,k,n,1);
        return res;
    }
    
    void dfs(int depth,int maxDepth,int n,int start)
    {
        if(maxDepth==depth)
        {
            res.push_back(tmp);
            return;
        }
        for(int i=start;i<=n;i++)
        {
            tmp[depth]=i;
            dfs(depth+1,maxDepth,n,i+1);
        }
    }
};

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

C递归版的全排列和组合算法