2017校招真題線上程式設計-求和

題目

題目描述
輸入兩個整數 n 和 m，從數列1，2，3.......n 中随意取幾個數,使其和等于 m ,要求将其中所有的可能組合列出來
輸入描述:

每個測試輸入包含2個整數,n和m

輸出描述:

按每個組合的字典序排列輸出,每行輸出一種組合

示例1
輸入

5 5

輸出

1 4
2 3
5

           

解析

• 這種題目類似于LeetCode combination sum,應該比較熟悉掌握！

#include<iostream>
#include<vector>
using namespace std;

void help(vector<vector<int>> & res, vector<int> &vec, int i, int n, int m)
{
	if (m == 0&&i<=n)
	{
		res.push_back(vec);
		return;
	}

	if (m<0)
	{
		return;
	}

	for (int j = i; j < n;j++)
    {
		vec.push_back(j + 1);
		help(res, vec, j + 1, n, m - j - 1);
		vec.pop_back();
    }
	return;
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> res;
	vector<int> vec;
	help(res, vec, 0, n, m);
	for (int i = 0; i < res.size(); i++)
	{
		for (int j = 0; j < res[i].size(); j++)
			j==0?cout << res[i][j]:cout<<" "<<res[i][j];
		cout << endl;
	}
	return 0;
}
           

C/C++基本文法學習

STL

C++ primer