SOJ 1030: Sum It Up http://acm.scu.edu.cn/soj/problem.action?id=1030
题意不难理解，给出一个非递增序列和一个数t，从序列中找出所有的子序列满足之和等于t。序列中的数只能用一次并且不能出现重复的子序列。跟SOJ 1027相比这一道题有两个难点：
(1) 子序列的长度是变化的
这个不难解决，引入一个变量cal记录序号。
(2) 去掉重复的子序列
举个例子：t=4, 序列={4,3,2,2,1,1}. 如果不删除重复子序列，我们可以得到下面的树：
注意到我们需要删掉位于同一层并且值相等的结点。
代码如下：
#include<iostream> using namespace std; int *num; int *record; int flag; void sum(int t,int n,int str,int cal) { int i; if (t == 0) { flag = 1; for (i = 0; i < cal - 1; i++) printf("%d+", record[i]); printf("%d\n", record[i]); } else { for (i = str; i < n; i++) { if (i>str && num[i] == num[i - 1]) continue; if (t >= num[i]) { record[cal] = num[i]; sum(t - num[i], n, i + 1,cal+1); } } } } int main() { int t, n; int i; while (scanf("%d%d", &t, &n) == 2 && n) { num = new int[n + 1]; record = new int[n + 1]; flag = 0; for (i = 0; i < n; i++) scanf("%d",&num[i]); printf("Sums of %d:\n",t); sum(t, n, 0,0); if (flag == 0) printf("NONE\n"); } return 0; }
原文：https://www.cnblogs.com/ClearMoonlight/p/10455784.html
