C再帰版の全配列と組合せアルゴリズム


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 1 3 3 1 3 1 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);
        }
    }
};