C再帰版の全配列と組合せアルゴリズム
For example,
全配置:
1から再帰し、2に対して再帰し、最後に3に対して再帰する.
順番は、1 2 3 1 3 2 1 3 3 1 3 1 3 1を先に出力する・・・ちょっと分析して出てきました
似たような組み合わせアルゴリズムもあります.こちらは1.です.n数のK配列
[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);
}
}
};