[C++]69391--和を求める

目次

例題説明

解題構想

コード実装

例題の説明
2つの整数nとmを入力し、数列1，2，3.......nの中から任意に数を取り、和をmとし、その中のすべての可能な組み合わせを列挙することを要求する.

入力説明:試験入力ごとに2個の整数を含むnおよびm.

出力記述:組み合わせごとに辞書順に並べて出力し、行ごとに組み合わせを出力する.

例1:

入力:5 5

出力:1 42 35

問題を解く構想.
再帰的実現に基づくdfs(深さ優先探索)でよい.これは典型的なリュックサックの問題です.
問題の解をF(n, m)とすると,2つのサブ問題に分解できるF(n-1, m-n)とF(n-1, m)の2つの問題を再帰的に解く.
解を求める過程で、条件を満たす数字の組み合わせが見つかった場合、例えば1, 2, 3, 4, 5を印刷し、何種類の組み合わせの和が5であるかを求める.1この要素については、結果に入れられる可能性があり、結果に入れない可能性があります.

結果に入れると、求めるに相当する2...5いくつかの数字の和をとる4.(すなわちF(n-1, m-n))

結果に入れなければ、求めることに相当する2...5いくつかの数字の和をとる5.(すなわちF(n-1, m))

コード実装

#include <iostream>
#include <vector>

using namespace std;

void help(int n, int m, vector<int>& v, int beg) {
	// m == 0        .    v               .    v           .
	if (m == 0) {
		for (int i = 0; i < v.size(); i++) {
			//    ? :                  .
			i == 0 ? cout << v[i] : cout << " " << v[i];
		}
		cout << endl;
	}
	for (int i = beg; i <= n && i <= m; i++) {
		//              .      .
		//     i -> n          m,        
		// i + 1 -> n          m - i
		v.push_back(i);
		help(n, m - i, v, i + 1);
		v.pop_back();
	}
}
int main() {
	int n, m;
	while (cin >> n >> m) {
		vector<int>v;
		help(n, m, v, 1);
	}
}

リンク:https://www.nowcoder.com/questionTerminal/11cc498832db489786f8a03c3b67d02c