给你一笔钱，找出可以用这些货币表示的所有不同形式

2019独角兽企业招聘Python工程师标准>>>

RMB有1、2、5、10、20、50、100个币右上角有20000面额的币种，给你一个钱右上角有20000面额的币种，找到所有这些货币可以表示的不同形式（例如 5=5 *1=2*2+1=2*1+1*3=1*5）

思考：应该考虑回溯

/*=========================================================*\
人民币有1、2、5、10、20、50、100的币种，给你一个钱的数目，
求出用这些币种能表达出的所有不同形式（例如5=5*1=2*2+1=2*1+1*3=1*5）
\*=========================================================*/
#include 
#include 
using namespace std;
int a[7]={1,2,5,10,20,50,100};
int temp[7]={0,0,0,0,0,0,0};
int n,j,z;
void change(int sum, int index) {
	int i;
	if (sum==n) {
		int k=0;
		for (j=0;j<7;j++) k+=temp[j];
		if (k>100) return;
		z++;
		cout << setw(8) << z << ":";
		for (j=0;j<7;j++)
			cout << temp[j];
		cout << endl;
		return;
	} else if (sum>n) return;
	else for (i=index;i<7;i++) {
		temp[i]++;
		change(sum+a[i],i);
		temp[i]--;
	}
}
int main(){
	n=5;
	z=0;
	change(0,0);
	system("pause");
	return 1;
}

转载于：