89.错账 (15分)

                  88.错账 (15分)
C时间限制:3 毫秒 | C内存限制:3000 Kb
题目内容:
某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某1笔或几笔。如果已知明细账目清单,能通过编程找到漏掉的是
哪1笔或几笔吗?
如果有多种可能,则输出所有可能的情况。
输入描述
第一行是有错的总金额,接下来是一个整数n,表示下面将要输入的明细账目的条数。
再接下来是n行整数,分别表示每笔账目的金额。为了方便,这里假设所有的金额都是整数;每笔金额不超过1000,金额的明细条
数不超过100。

输出描述
所有可能漏掉的金额组合。每个组合1行。组合之间,按首数据在输入中的次序决定组合的先后,如果首数据是同一个,则看下一
个数据的位置。每组金额内部的几个数据按照值从小到大排列,中间用空格分开。

输入样例
6
5
3
2
4
3
1

输出样例
3 4
1 3 3
1 2 4

思路:直接dfs,按顺序搜索,搜到的结果排序, 同时用set判重,注意每行输入末尾不能有空格。

set使用vector的例子:

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

int main(){
	set<vector<int> > myset;
	
	vector<int> a;
	a.push_back(2);
	myset.insert(a);
	vector<int> b;
	b.push_back(2);
	myset.insert(b);
	cout << myset.size() <<endl;
//	cout << myset.find(b) << endl;
	vector<int> c;
	cout << myset.count(c) <<endl;
	
	return 0;
}

  

本题代码:

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
int mon[105];
int lou, k;
set<vector<int> > myset;

void dfs(int x, int sum, int tep[], int ct){
	if(x > k){
		return ;
	}
	if(sum == lou){
		sort(tep, tep + ct);
		vector<int> aa;
		for(int i = 0; i < ct; i++){
			aa.push_back(tep[i]);
//			cout << tep[i] << " ";
		}
		if(myset.count(aa) == 0){
			myset.insert(aa);
			cout << tep[0];
			for(int i = 1; i < ct; i++){
				cout << " " << tep[i] ;
			}	
			cout << endl;
		}
		return ;
	}
	tep[ct] = mon[x];
	dfs(x + 1, sum + mon[x], tep, ct + 1);
	dfs(x + 1, sum, tep, ct);
}

int main(){
	int tep[105];
	cin >> lou >> k;
	int sum = 0;
	for(int i = 0; i < k; i++){
		cin >> mon[i];
		sum += mon[i];
	}
	lou = sum - lou; 
	
	dfs(0, 0, tep, 0);
	
	return 0;
}

  

 

上一篇:LeetCode 89. 格雷编码


下一篇:python---实现多个有序列表的合并