当前位置: 代码迷 >> 综合 >> POJ1564 Sum It Up(DFS)
  详细解决方案

POJ1564 Sum It Up(DFS)

热度:20   发布时间:2024-01-16 13:55:45.0

题意:

输入一组数,要求输出总数为t的所有组合

要点:

因为数最多只有12个,直接暴力搜索就可以了,还有要判断重复,就是与前一个比较,但是其实只是剪枝提升速度,4,3,2,1,2,1这种还是会输出两个4,2,1这种


15167723 Seasonal 1564 Accepted 164K 16MS C++ 709B 2016-02-16 21:40:14
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n, t;
int num[15], end[15];
bool flag;  //利用flag判断有没有组合void dfs(int k,int len,int last)//k作为当前下标,都只一直往前搜索,last是剩余值,len是路径的记录
{if (last == 0){flag = false;for (int i = 0; i < len; i++){if (i == 0)printf("%d", end[i]);elseprintf("+%d", end[i]);}printf("\n");return;}for (int i = k; i < n; i++){if (i == k || (num[i] != num[i - 1] && last - num[i] >= 0))//判断是否与前一个重复,常用剪枝{end[len] = num[i];dfs(i + 1, len + 1, last - num[i]);}}
}int main()
{while (scanf("%d%d", &t, &n) != EOF, t + n){flag = true;for (int i = 0; i < n; i++)scanf("%d", &num[i]);printf("Sums of %d:\n", t);dfs(0, 0, t);if (flag)printf("NONE\n");}return 0;
}


  相关解决方案