c – 使用递归和回溯来生成所有可能的组合

我试图实现一个类,它将生成所有可能的无序n元组或组合,给出了许多元素和组合的大小.

换句话说,当调用这个时：

NTupleUnordered unordered_tuple_generator(3,5,print);
unordered_tuple_generator.Start();

print()是在构造函数中设置的回调函数.
输出应为：

{0,1,2}
{0,3}
{0,4}
{0,2,3,4}
{1,3}
{1,4}
{2,4}

这是我到目前为止

class NTupleUnordered {
public:
    NTupleUnordered( int k,int n,void (*cb)(std::vector<int> const&) );
    void Start();
private:
    int tuple_size;                            //how many
    int set_size;                              //out of how many
    void (*callback)(std::vector<int> const&); //who to call when next tuple is ready
    std::vector<int> tuple;                    //tuple is constructed here
    void add_element(int pos);                 //recursively calls self
};

而这是递归函数的实现,Start()只是一个kick启动函数来有一个更清晰的接口,它只调用add_element(0);

void NTupleUnordered::add_element( int pos )
{

  // base case
  if(pos == tuple_size)
  {
      callback(tuple);   // prints the current combination
      tuple.pop_back();  // not really sure about this line
      return;
  }

  for (int i = pos; i < set_size; ++i)
  {
    // if the item was not found in the current combination
    if( std::find(tuple.begin(),tuple.end(),i) == tuple.end())
    {
      // add element to the current combination
      tuple.push_back(i);
      add_element(pos+1); // next call will loop from pos+1 to set_size and so on

    }
  }
}

如果我想生成一个常数N大小的所有可能组合,可以说我可以做的大小3的组合：

for (int i1 = 0; i1 < 5; ++i1) 
{
  for (int i2 = i1+1; i2 < 5; ++i2) 
  {
    for (int i3 = i2+1; i3 < 5; ++i3) 
    {
        std::cout << "{" << i1 << "," << i2 << "," << i3 << "}\n";
    }
  }
}

如果N不是常数,则需要一个模仿上述的递归函数
通过在自己的框架中执行每个for-loop功能.当循环终止时,
程序返回到前一帧,换句话说,回溯.

我总是有递归的问题,现在我需要将其与回溯结合起来,以生成所有可能的组合.任何指针,我做错了什么？我应该在做什么或我俯瞰？

P.S：这是一个大学作业,也包括基本上对订购的n元组做同样的事情.

提前致谢！

////////////////////////////////////////////////// ///////////////////////////////////////

只是想跟进正确的代码,以防万一有人想知道同样的事情.

void NTupleUnordered::add_element( int pos)
{

  if(static_cast<int>(tuple.size()) == tuple_size)
  {
    callback(tuple);
    return;
  }

  for (int i = pos; i < set_size; ++i)
  {
        // add element to the current combination
        tuple.push_back(i);
        add_element(i+1); 
        tuple.pop_back();     
  }
}

对于有序n元组的情况：

void NTupleOrdered::add_element( int pos )
{
  if(static_cast<int>(tuple.size()) == tuple_size)
  {
    callback(tuple);
    return;
  }

  for (int i = pos; i < set_size; ++i)
  {
    // if the item was not found in the current combination
    if( std::find(tuple.begin(),i) == tuple.end())
    {
        // add element to the current combination
        tuple.push_back(i);
        add_element(pos);
        tuple.pop_back();

    }
  }
}

谢谢Jason的全面回应！

root
                        ________|___
                       |            | 
                     __1_____       2
                    |        |      |
                  __2__      3      3
                 |     |     |      |
                 3     4     4      4

{1,4}

void recursive_comb(int step_val,int array_index,std::vector<int> tuple);

void init_combinations()
{
    std::vector<int> tuple;
    tuple.reserve(tuple_size); //avoids needless allocations
    recursive_comb(tuple_size,tuple);
}

void recursive_comb(int step_val,std::vector<int> tuple)
{
    if (step_val == 0)
    {
        all_combinations.push_back(tuple); //<==We have the final combination
        return;
    }

    for (int i = array_index; i < set.size(); i++)
    {
        tuple.push_back(set[i]);
        recursive_comb(step_val - 1,i + 1,tuple); //<== Recursive step
        tuple.pop_back(); //<== The "backtrack" step
    }

    return;
}