2018小米秋招笔试题-24点

题目描述

链接：https://www.nowcoder.com/questionTerminal/263fa05acac5424a91214694a1c1eb8f

有n个1~23的整数，写一个算法，求出有多少个相互不同的子集合的和为24点。

• 输入描述:

输入数据包含一组
每组的第一行包括一个整数n(1 <= n <= 23)
第二行包括n个整数1 <= 整数 <= 23）

• 输出描述:

对于每个测试实例，要求输出能组成24点的所有子集合的数量（子集合相互不同）。如果不存在，则输出0。每个测试实例的输出占一行。

示例1

• 输入

4
1 2 22 23

• 输出

2

参考代码

#include <iostream>
#include <set>
using namespace std;
set<set<int>> res;
int GetSum2(int a[], int n, bool visited[])
{
int num = 0;
for (size_t i = 0; i < n; i++)
{
if (visited[i])
num += a[i];
}
return num;
}
void Print2(int a[], int n, bool visited[])
{
set<int> tmp;
for (size_t i = 0; i < n; i++)
{
if (visited[i])
tmp.insert(a[i]);
}
res.insert(tmp);
}
void GetSubSet2(int a[], int n, int m, int begin, bool visited[])
{
if (begin == n)
{
if (GetSum2(a, n, visited) == m)
{
Print2(a, n, visited);
}
return;
}
visited[begin] = true;
GetSubSet2(a, n, m, begin + 1, visited);
visited[begin] = false;
GetSubSet2(a, n, m, begin + 1, visited);
}
int main(int argc, char const *argv[])
{
int n;
cin >> n;
int *a = new int[n];
bool *visited = new bool[n];
for(int i = 0;i < n;i++){
cin >> a[i];
visited[i] = false;
}
GetSubSet2(a, n, 24, 0, visited);
cout << res.size() <<endl;
return 0;
}

最后

以上就是友好人生为你收集整理的2018小米秋招笔试题-24点的全部内容，希望文章能够帮你解决2018小米秋招笔试题-24点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。