问题描写叙述

一个战士打了10次靶。一共打了90环，问一共同拥有多少种可能，并输出这些可能的组合。

思路

首先。嵌套10层循环进行穷举是不可取的，一是由于速度太慢，二是假设改成打20次靶就完蛋了。

事实上这就是一个树的搜索问题。

1. 设第一次打了0环。那么第二次可能打0 ~ 10环这些可能

2. 以第一次打的0环为root，将第二次全部可能的环数都做为root的子结点

3. 反复1, 2步

这样就构成了一棵树。表示当第一次打了0环时全部的可能性。

我们要做的就是从上到下遍历这棵树。当经过的结点之和等于90时，即命中。

然后再将根结点值改成1，直到10。

那么问题来了，一棵树须要遍历多少种组合呢？设打靶次数为t, 那么全部的组合数 = 1+(11)t−1=1+(11)9 种。这个结果已经超过了4亿, 显然全部遍历一遍时间上是不能忍的。我们能够通过剪枝思想来去掉部分不必要的遍历，即推断一下即便以后全打10环时能不能满足90环的要求，假设不能则不须要继续递归了。

另一个问题，我们真的要手动创建一个树形数据结构来运行上面的过程吗？假设这样做理论上是没问题的，可是会消耗大量的内存。 事实上我们能够使用递归的方式来模拟树的遍历。

实现

定义方法

int shoot(int score, int left, int totalScores, Dequeue
      
        path)
      

表示已经打了score环。还要打left枪，总环数为totalScores时全部的结果数。这里path是一个栈数据结构。用来记录递归调用的路径，从而记录了一次可能组合的各个环数。

完整代码例如以下：

public class Main {
          public static int SHOOT_TIMES = 10;    public static void main(String[] args) {        System.out.println(shoot(0, SHOOT_TIMES, 90, new LinkedList<>()));    }    /**     * 返回打score环且仅仅能打left枪且总环数为TOTAL_SCORES的全部结果数     * @param score     * @param left     * @param path     * @return     */    public static int shoot(int score, int left, int totalScores, Deque
      
        path) {        int tot = 0;        if (1 == left) {            // 剪枝            // 去掉明显不可能的结果            // 即在最后一枪时计算距离90环还剩下的环数，            // 假设环数大于10。则不可能打满            int left_scores = totalScores - score;            // 当剩下的环数在0 ~ 10之间时。表明这是一个可取的组合            if (left_scores >= 0 && left_scores <= 10) {                path.push(left_scores);                printStack(path);                path.pop();                ++tot;            }            path.pop();            return tot;        }        for (int i = 0 ; i <= 10 ; ++i) {            // 剪枝.            // 计算已经打了score环时还剩下多少环.            // 假设即便剩下全打10环还打不满90环，则表示这不是一个可取的结果            if (totalScores - (score + i) <= 10 * left) {                path.push(i);                tot += shoot(score + i, left - 1, totalScores, path);            }        }        if (false == path.isEmpty()) {            path.pop();        }        return tot;    }    /**     * 打印出栈内的全部元素     * @param list     */    private static void printStack(Deque
       
         list) {        int ix = 0;        int LEN = list.size();        for (Integer n : list) {            if (ix == LEN - 1) {                System.out.printf("%d\n", n);                break;            }            System.out.printf("%d, ", n);            ++ix;        }    }}