一、题目

题目描述

某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某 1 笔或几笔。如果已知明细账目清单，能通过编程找到漏掉的是哪 1 笔或几笔吗？

如果有多种可能，则输出所有可能的情况。

输入描述

用户输入的第一行是：有错的总金额。

接下来是一个整数

再接下来是

为了方便，不妨假设所有的金额都是整数；每笔金额不超过 1000，金额的明细条数不超过 100。

输出描述

所有可能漏掉的金额组合。每个情况 1 行。金额按照从小到大排列，中间用空格分开。

二、我的思路

　　1、首先按题目要求将数据接收存放到数组里面，然后使用冒泡排序将每一笔的金额从小到大排序。

　　2、使用递归遍历每一种金额的组合。

　　3、在遍历每一种组合的时候，当遇到了需要的金额，如果在新的数组里没有该组合，将该组合放到新的数组里面。

　　4、当存放完成后，输出该组合到屏幕上，然后退出该分支。

三、代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int length = 1000;
int loal = 0;

string* str = new string[length];

//a[]是数组	x是上一级的金额	N是一共有多少笔钱	  n是循环开始  set是标记数组	em是要的金钱
void dfs(int a[], int x, int N, int n, int em, char set[]) {
	if (x == em) {
		//当当前的存储长度小于总长度时可以进行存储操作
		if (loal < length) {
			string strcmp_1;
			//先将set数组的值放到strcmp_1数组里面
			for (int i = 0; i < N; i++) {
				if (set[i] != '0') {
					strcmp_1 += set[i];
				}
			}
			//遍历当前的str，查看是否有一样的，如果没有就输出set(当前的符合题目输出的数组)
			int t = 0;
			for (t = 0; t < loal; t++) {
				//使用临时存储的strcmp_1与str中的所有字符串比较，如果有一样的那就跳出循环
				if (!strcmp(strcmp_1.c_str(), str[t].c_str())) {
					break;
				}
			}
			//如果t>大于当前的loal说明没有相同的
			if (t >= loal) {
				//将当前的strcmp_1存放到str中
				str[loal] = strcmp_1;
				loal++;
				//输出当前的组合
				for (int i = 0; i < N; i++) {
					if (set[i] != '0') {
						cout << set[i] << " ";
					}
				}
				cout << endl;
			}
		}
		return;
	}

	//递归使用递归进入每一种组合的分支
	for (int i = n; i < N; ++i) {
		set[i] = a[i] + '0';
		dfs(a, a[i] + x, N, ++n, em, set);
		set[i] = '0';
	}
}

int main()
{
	// 请在此输入您的代码
	//每笔金额的数组
	int a[100];

	//存放修改该后的数组
	char set[1000];

	//给数组清零
	memset(set, '0', sizeof(set));

	//一共多少笔
	int mark = 0;

	//错误的金额
	int jing = 0;

	//全部钱加起来
	int sum = 0;

	cin >> jing;
	cin >> mark;

	//输入每笔金额
	for (int i = 0; i < mark; i++) {
		cin >> a[i];
		sum += a[i];
	}
	//先使用冒泡排序，由 小到大排序
	int temp = 0;
	for (int i = 0; i < mark; i++) {
		for (int j = i; j < mark; ++j) {
			if (a[i] > a[j]) {
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
	//使用递归
	dfs(a, 0, mark, 0, sum - jing, set);

	return 0;
}