/* C时间限制：1 毫秒 | C内存限制：65535 Kb题目内容： 对于由从1到N(1<=N<=39)这N个连续的整数组成的集合来说，我们有时可以将集合分成两个部分和相同的子集合。例如，N=3时，可以将集合{1,2,3}分为{1,2}和{3}。此时称有一种方式（即与顺序无关）。N=7时，共有四种方式可以将集合{1,2,3,...,7}分为两个部分和相同的子集合：{1,6,7}和{2,3,4,5}{2,5,7}和{1,3,4,6}{3,4,7}和{1,2,5,6}{1,2,4,7}和{3,5,6}输入描述程序从标准输入读入数据，只有一组测试用例。如上所述的N。输出描述方式数。若不存在这样的拆分，则输出0。输入样例7输出样例4*///方法一：dfs(会超时) #include #include #include #include using namespace std;set str;int n, r_sum;long long ct = 0;string visit;void dfs(int sum, int start){ if(sum > r_sum){ return ; } if(sum == r_sum){// cout << "ct: " << ct << endl;// cout << visit << "sum = r_sum" << endl; if(str.count(visit) == 0){ str.insert(visit);// cout << "init " << visit << endl; ct++; } return ; } for(int i = start; i <= n; i++){ if(visit[i - 1] == '0'){ visit[i - 1] = '1'; dfs(sum + i, i); visit[i - 1] = '0'; } }}int main(){ cin >> n; for(int i = 0; i < n; i++) visit += '0'; int sum = 0; sum = (n + 1) * n / 2; if(r_sum % 2 == 1){ cout << 0; return 0; } r_sum = sum / 2; dfs(0, 1); if(ct >= 2) cout << ct / 2 << endl; else cout << 0 << endl; return 0;}//方法二：dp(类似01背包，当然可以试一下完全用01背包解答)#include using namespace std;int dp[10000000];int main(){ int n, sum = 0; cin >> n; for(int i = 1; i <= n; i++) sum += i;// cout << sum; if(sum / 2 * 2 != sum){ //若sum为奇数则直接cout 0 cout << 0 << endl; return 0; } sum /= 2; dp[0] = 1; //初始化一个 for(int i = 1; i <= n; i++) for(int j = sum; j >= i; j--) dp[j] += dp[j - i]; cout << dp[sum] / 2 << endl; return 0;}