顾名思义，剪枝就是通过一些判断，剪掉搜索树上不必要的子树。在采用DFS算法搜索时，有时候我们会发现某个结点对应的子树的状态都不是我们要的结果，这时候我们没必要对这个分支进行搜索，砍掉这个子树，就是剪枝。
      在DFS搜索算法中，剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。应用剪枝策略的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。

     剪枝策略按照其判断思路可大致分成两类：可行性剪枝及最优性剪枝。

      1.可行性剪枝

     可行性剪枝就是把能够想到的不可能出现的情况给它剪掉 。该方法判断继续搜索能否得出答案，如果不能直接回溯。

【例1】Sum It Up （POJ 1564）

Description

Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.
Input

The input will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x 1 , . . . , x n . If n = 0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and x 1 , . . . , x n will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.
Output

For each test case, first output a line containing `Sums of', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line `NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice.
Sample Input

4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0
Sample Output

Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25

      （1）编程思路。

      由于题中给出待选数的顺序就是从大到小的，因此我们从第一个数开始，依次往后搜索，将可能的数据都记录下来，每遇到一种满足题意的组合就输出，一直搜索下去，得到所有答案。若没有答案，输出NONE。

      定义全局数组int a[12]来保存给出的待选数列表，为输出和式，定义int b[12]保存选中的数据。

      递归函数void dfs(int i,int j,int sum)表示从数组a的第i个元素开始选择数据加入到和值sum中，选中的数据a[i]保存到b[j]中。

      因为题目中所有待选数都是正数，因此一旦发现当前的和值sum都已经大于t了，那么之后不管怎么选，和值都不可能回到t，所有当sum > t时，可以直接剪掉。

       if  (sum > t)   return;

    由于给出的N个数中可以有重复的数，求N个数中取若干个数，这若干个数的和为T的所有情况，但这些情况不能重复。因此，程序中还需要去重。

      如果不去重，则对于第1组测试数据4 6 4 3 2 2 1 1，会输出

Sums of 4:
4
3+1            // 式子中的1是倒数第2个1
3+1            // 式子中的1是最后1个1
2+2
2+1+1       // 式子中的2是第3个2
2+1+1       // 式子中的2是第4个2

由于待选数从大到小排列，相同的数据连续放在一起，因此用循环

            while(k<n && a[k]==a[k+1])     k++;

可以简单地去重。即某个数作为和式中的加数第1次被选中时，其后连续相同的数不能作为和式中的第1次被选中的加数。

      这个去重操作也会剪掉一些枝叶，也可以看成是一个剪枝。

      （2）源程序。

#include <stdio.h>

#define N