WY15 幸运的袋子
中等 通过率：18.85% 时间限制：1秒 空间限制：32M
描述
一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。 例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3 你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。
输入描述：
第一行输入一个正整数n(n ≤ 1000) 第二行为n个数正整数xi(xi ≤ 1000)
输出描述：
输出可以产生的幸运的袋子数
示例
输入：
3
1 1 1输出：
2解题思路：回溯 + 剪枝
还是一样的老套路，但是这次我们在变的不是 vector，而是利用 sum、multi 两个变量分别代表和与积，这样子可以省略很大的空间。
这道题无非就是要我们找出所有的组合，判断一下这些组合是否幸运，而其实最重要的是还有一点，就是如果我们想让 a+b > a*b，那么我们只能有一种情况，就是 a 和 b 之间必须有一个是 1，其它的情况都不能成立，通过这个条件，我们就可以做剪枝操作，也就是我们在这个判断和的时候，如果这个和中出现的几个数字，超过了一个非 1 数字的话，那么其实就不会成立了，这就是我们的剪枝条件！
剩下的就是去重，因为我们不能重复组合，所以我们可以用 while 循环去重！
#include<iostream>
#include<algorithm>
using namespace std;
/*
getLuckyPacket:从当前位置开始搜索符合要求的组合，一直搜索到最后一个位置结束
x[]: 袋子中的所有球
n: 球的总数
pos: 当前搜索的位置
sum: 到目前位置的累加和
multi: 到目前位置的累积值
*/
int getLuckyPacket(int x[], int n, int pos, int sum, int multi)
{
int count = 0;
// 循环，搜索以位置i开始所有可能的组合
for (int i = pos; i<n; i++)
{
sum += x[i];
multi *= x[i];
if (sum > multi)
{
// 找到符合要求的组合，加1，继续累加后续的值，看是否有符合要求的集合
count += 1 + getLuckyPacket(x, n, i + 1, sum, multi);
}
else if (x[i] == 1)
{
// 如果不符合要求，且当前元素值为1，则继续向后搜索
count += getLuckyPacket(x, n, i + 1, sum, multi);
}
else
{
// 如果sum大于multi,则后面就没有符合要求的组合了
break;
}
// 回溯，要搜索下一个位置之前，首先恢复sum和multi
sum -= x[i];
multi /= x[i];
// 去重，数字相同的球，没有什么区别，都只能算一个组合，所以直接跳过
while (i < n - 1 && x[i] == x[i + 1])
{
i++;
}
}
return count;
}
int main()
{
int n;
while (cin >> n)
{
int x[n];
for (int i = 0; i < n; i++)
{
cin >> x[i];
}
sort(x, x + n); // 去重得先排序
//从第一个位置开始搜索
cout << getLuckyPacket(x, n, 0, 0, 1) << endl;
}
return 0;
}