黑马程序员技术交流社区

标题: 求问这道题目的解题思路，万分感谢啊！！ [打印本页]

---

作者: OCTSJimmy    时间: 2014-11-16 10:33
标题: 求问这道题目的解题思路，万分感谢啊！！
这道题，假如在不使用暴力搜索的前提下（也就是需要保证效率的情况下），怎么解决呢？
本来想用组合来求解，得出了公式：∑(1->i)C(n,i) 其中 i = n - 1，到这里就卡壳了，后面完全没头绪啊。

题目：
* 晓萌希望将1到N的连续整数组成的集合划分成两个子集合，且保证每个集合的数字和是相等。
* 例如，对于N=3，对应的集合{1，2，3}能被划分成{3} 和 {1,2}两个子集合.
* 这两个子集合中元素分别的和是相等的。
* 对于N=3，我们只有一种划分方法，而对于N=7时，我们将有4种划分的方案。
* 输入包括一行，仅一个整数，表示N的值（1≤N≤39）。
* 输出包括一行，仅一个整数，晓萌可以划分对应N的集合的方案的个数。当没发划分时，输出0。
* 样例输入
* 7
* 样例输出
* 4

非常感谢大家！谢谢！

---

作者: cs8630323    时间: 2014-11-16 17:27


以前一道测试题，“abcd”，把字符串字母所有组合列出来，觉得思路差不多，计算出1-N的总和，用递归枚举所有可能的集合组合，计算某个枚举的集合的和，集合的和*2=总和，就加1.

---

作者: 爱学习的小明    时间: 2014-11-16 18:19
思路：
1.先求N个数的相加的和，模与2，等于1，这个N不能满足两个集合和相等，模与2结果为0，则继续；
2.得到这个N个数所有的组合，计算所有组合的和，等于N个数的和除以2的结果，就用计数一次

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2