请教一道简单的算法题

[levelworm]

题目大致上是这样的，两个砝码分别重 a 和 b，a 和 b 不等，放在一块称重量，可以称 a+b 或者 a-b 的货物（假设 a 更大一些）。那么，假设手上有 N 个重量不等的砝码，可以称哪些重量？要求用递归。

举例：手上有 1, 4, 9 三个砝码，那么可以称 3, 5, 8, 10, 13 五种重量的货物。

这道题目我倒是做出来了，但是感觉效率很低：

大致上是两个函数，第二个是真正的递归函数：

用的是自己写的伪代码，所谓insert()就是把两个砝码能够称的重量塞进一个 set 中（这样就不会有重复了），而 a exclude A 就是集合 a 把 A 元素去除掉之后得到的子集合。

void generateWeights(set<int> a) {
		if (a.size() == 2) {
			insert(X+a1, X-a1);
		}
		else {
			for A in a {
				generateWeightsHelper(A, a exclude A);
			}
		}
	}

void generateWeightsHelper(int b, set<int> a) {
	if (a.size() == 1) {
		insert(b+a, a-b);	// assuming a>b
	}
	else {
		for A in a {
			generateWeightsHelper(b, a exclude A);
		}
	}
}

然后我自己设想了一个案例，跟着函数走了一遍，发现重复运算的很多，比如说 insert(3, 5)就出现了两次。

Example: (1, 4, 9, 15)

Step 1 - generateWeightsHelper(1, (4, 9, 15))
	Step 1.1 - generateWeightsHelper(1, (4, 9))
		Step 1.1.1 - generateWeightsHelper(1, 9) -> Insert(8, 10)
		Step 1.1.2 - generateWeightsHelper(1, 4) -> Insert(3, 5)
	Step 1.2 - generateWeightsHelper(1, (4, 15))
		Step 1.2.1 - generateWeightsHelper(1, 4) -> Insert(3, 5)
		Step 1.2.2 - generateWeightsHelper(1, 15) -> Insert(14, 16)
	Step 1.3 - generateWeightsHelper(1, (9, 15))
		Step 1.3.1 - generateWeightsHelper(1, 9) -> Insert(8, 10)
		Step 1.3.1 - generateWeightsHelper(1, 15) -> Insert(14, 16)
Step 2 - generateWeightsHelper(4, (1, 9, 15))
	// 略
Step 3 - generateWeightsHelper(9, (1, 4, 15))
	// 略

请问有什么办法可以把这些重复的去掉？如果能够有想法就最好了。

[daozhihun]

重复的你可以用一个 map 来记录算过的，以后碰到了算过的直接取出结果 return 避免重复递归

[binux]

为什么我不能单独用一个 4 的砝码称重？

[binux]

而且不能同时用 3 个砝码，太简单了，列举 combinations 就完了。

[Vegetable]

这不是在算重量，而是让你找出砝码所有的不同摆放方式，再分别计算两边的质量差就完了。
正如 @binux 说的，连用一个都不行，每次都是全员登场。

[Vegetable]

由于天平只有两边，所以一边确定，另一边也确定了。
那么就是列出 N 个砝码时，其中一边分别放 1 、2 、3...N 个（其实放到一半就行）的方案，就是排列组合那一套。

[misdake]

1.
你看你的代码，你得到的结果似乎是“假设手上有一些重量不等的砝码，使用 2 个砝码来称重(不多不少，必须是 2 个)，可以称哪些重量”
而不是“假设手上有 N 个重量不等的砝码，可以称哪些重量”

2.
你碰到的重复计算的来源是：每一次想要扔掉一个元素的时候，都遍历整个集合
会出现“先扔掉 1 再扔掉 2”和“先扔掉 2 再扔掉 1”的两种调用，但谁先谁后在这道题中无所谓，重复计算了。
为了避免重复计算，应当舍弃掉这两种情况中的 1 种，如总是要求“扔掉的数字必须必上一次扔掉的数字更大”

[BiteTheDust]

很基础的背包问题 01 背包稍微变形下就可以了

[levelworm]

@misdake @binux @Vegetable 多谢，我觉得楼上的朋友们说的有道理，应该允许单个或者多于两个砝码称重，虽然题目没说但是常理来看应该允许。我晚上重新写一下。

[levelworm]

@misdake 我又想了一下，如果允许任意数量的砝码，按照上面 @Vegetable 网友的提示，实际上是考摆放，那么我需要区分左右盘，因为只能右盘的砝码重量多过左边，而不能相反（假设货物固定在左边）。

按照递归的常规思路，首先确认一个最简情况，就是如果只有一个砝码 a，那么就只能放在右边, Ra 。然后，我有(1, 4, 9, 15)四个砝码，假设我已知(1, 4, 9)所有的摆放组合(R1, R4, R9, L1R4, L1R9, L1R49, etc...)，那么增加第四个砝码 15 之后，我能做的就是在所有这些组合里头都把 15 往左右放放试试看（去掉左边太重的结果），再加上 1，4，9 放左边，15 放右边这个结果，以及 15 单独放右边的结果，应该就得到所有的组合了。

不知道我这个思路对头吗？总觉得那么别扭呢。。。