蓝桥杯 ——无重复组合——C++

问题描述：

求任意长度的（ABCD.....）全部n=0,1,2 ....组合情况(n小于等于串的长度)

解决思路：

1. 如果串的长度固定，n的值固定循环嵌套
   
2. 在这里以深度优先形成一棵树，如下图：

 

源代码：

#include<iostream>
#include<cstring>
using namespace std;
int N=0;  //计算组合数 
string X;   //待排序的字符串 
string R="";//存放结果的字符串 
//  k 处理的位置
//  goal  从目的串中要取的元素数         在这里也可以理解为递归的深度 
// 该函数以深度优先形成一棵树，且树杈数随着的变化K而变化 
void Combination(int k,int goal) 
{
    if(goal==0)//出口 
    {
        cout<<R<<endl;
        N++;
        return;
    }
    for(int i=k; i<X.length(); i++ )//控制树杈数 
    {    
        string r;
        r=R;
        R=R+X[i];
        Combination(i+1,goal-1); 
        R=r;  //回溯 
    }
}
int main()
{   
    int goal;
    cin>>X;
    cin>>goal;
    Combination(0,goal);
    cout<<N<<endl;
    return 0;
}

 运行结果：