欢迎关注Hadoop、Spark、Flink、Hive、Hbase、Flume等大数据资料分享微信公共账号:iteblog_hadoop
  1. 文章总数:978
  2. 浏览总数:11,978,658
  3. 评论:3938
  4. 分类目录:106 个
  5. 注册用户数:6129
  6. 最后更新:2018年12月15日
过往记忆博客公众号iteblog_hadoop
欢迎关注微信公众号:
iteblog_hadoop
大数据技术博客公众号bigdata_ai
大数据猿:
bigdata_ai

正整数n的所有可能和式的组合

  很多人在面试中会被问到这样的题目,题目的含义是有如下的组合4=1+1+1+1、1+1+2、1+3、2+1+1、2+2。光从题目来看有两种理解:

将3 = 1 +2 和3 = 2 +1当作不同的组合。这种情况是比较简单的,直接将给定的n递归地分解成(n - 1) + 1当递归求得的结果和我们需要分解的整数n相等,则这次分解就完成了,我们可以把分解的组合输出来,然后返回。一直递归到n不能再分解(也就是分解成了n个1)。

#include <iostream>
#include <vector>

// 过往记忆
// www.iteblog.com
// 转载请注明
using namespace std;

void add(int sum, int start, int tempSum, vector<int> &v){
  if(sum == tempSum){
    vector<int>::iterator it = v.begin();
    for(; it != v.end(); it++){
      cout << *it;
      if(it + 1 != v.end()){
        cout << " + ";
      }
    }

    cout << endl;
    return;
  }else if(sum < tempSum){
    return;
  }

  for(int i = sum; i > 0; i--){
    v.push_back(i);
    add(sum, i, tempSum + i, v);
    v.pop_back();
  }
}

void add(int sum){
  int tempSum = 0;
  vector<int> v;
  add(sum, sum, tempSum, v);
}

int main(){
  add(5);
  return 0;
}

运行的结果:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 3
2 + 2 + 1
2 + 1 + 2
2 + 1 + 1 + 1
1 + 4
1 + 3 + 1
1 + 2 + 2
1 + 2 + 1 + 1
1 + 1 + 3
1 + 1 + 2 + 1
1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1

如果把将3 = 1 +2 和3 = 2 +1当作相同的组合,这下相对来说比较难点,但是仔细分析,会发现,算法和上面的几乎一样,每次分解的数不再是从n开始,这样可以使得每次分解的数不会超过上一次分解出来的数,代码只修改了一个地方就可以实现:

#include <iostream>
#include <vector>

// 过往记忆
// www.iteblog.com
// 转载请注明 
using namespace std;

void add(int sum, int start, int tempSum, vector<int> &v){
  if(sum == tempSum){
    vector<int>::iterator it = v.begin();
    for(; it != v