计算一个数的所有组合数 代码(C++)

本文地址: http://blog.csdn.net/caroline_wendy

计算一个数的组合数, 使用递归进行求解.

如果计算3位的组合数, 首先任选固定一位, 然后计算其余两位的组合数, 最后组合至一起. 如 1 + [23, 32] = 123, 132;

在固定其余位数, 如 2 + [13, 31] = 213, 231; 3 + [12, 21] = 312, 321;

程序分为两步分, 一个删除任意位置的一个元素, 一个是递归求解组合数.

代码:

/*
 * Combination.cpp
 *
 *  Created on: 2014.6.9
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   
#include 
   
     #include 
    
      using namespace std; void deleteOneNum (std::string& _num, std::size_t _n) { if (_n >= _num.length()) { return; } string temp (_num.substr(_n+1)); _num = _num.substr(0, _n) + temp; } void combination (std::string _num, std::string _buff, std::vector
     
      & _result) { if (_num.length() <= 0) { _result.push_back(_buff); } for (std::size_t i=0; i<_num.length(); ++i) { std::string temp (_num); deleteOneNum(temp, i); combination(temp, _buff+_num[i], _result); } } int main (void) { std::string num("4123"); std::vector
      
        result; combination(num, "", result); for (std::size_t i=0; i
       
        

        输出:
        

        

        
4123
4132
4213
4231
4312
4321
1423
1432
1243
1234
1342
1324
2413
2431
2143
2134
2341
2314
3412
3421
3142
3124
3241
3214