题目: 组合总和
来自智得网
方法一：回溯法
该题目是解决组合问题，因为回溯法解决的问题主要范畴是组合问题或者排列问题，所以可以首先尝试使用回溯法解决。
算法流程
回溯法通用的算法模版如下：
回溯(路径，选择列表){
如果到达终止条件：
将该路径加入结果列表；
循环选择列表:
#将该选择添加到选择路径
路径.添加(选择)
回溯(路径, 选择列表)
# 撤销选择
路径.删除(选择）
}
本题需要所有的数字都是正数，否则无法求解，假如如果存在几个整数和几个负数的和为零的情况下，那么这个组合和可以重复任意次值都不会发生变化，从而结果是无限个。
数组中全是正数的情况，每次增加一个数字，和的值一定会增加。所以回溯的终止条件是和大于等于target。
回溯过程中每次的路径选择可以添加数组的任意数字。
方法二：动态规划
求解总数的问题可以考虑用动态规划求解。
动态规划一般分为确定变量，确定状态转移方程，确定边界条件等三个步骤。
- 确定状态和状态变量
- 分析问题特点，按照时间或者空间特征，将问题分为有序的若干阶段，因为动态规划是按顺序递推求解，所以阶段一定是可排序的。
- 确定问题每个阶段求解时的状态，确定所需要的变量。求解过程一般是确定dp数组以及下标的含义。
- 确定状态转移方程
- 分析决策过程，确定状态转移方程，决策和状态转移是相互联系的，状态是根据上一阶段状态以及当前决策变迁到当前状态的，所以确定决策就可以明确状态迁移方程，实际求解过程中，往往根据当前阶段和上一阶段的状态差异，推导决策过程。
- 确定边界条件
- 状态转移方程是递推的过程，所以需要确定递推的边界条件。因为递推过程是从前到后依次执行的，所以边界条件一般就是初始值。
动态规划法的状态变量可以使用和的具体具体值作为变量，所以假设和为n的解为f（n）。
如果和为target，那么最后一次取数一定是数组中存在的那些数字，所以f（n）应该是f（n-ai）的和。
边界条件是加入target的值是数组中最小的值ai，那么根据上面的推论f（ai）= f（0），因为为了该函数是自洽的，f（0）的值必须是1，所以f（0）可以作为边界值。
综上所述，状态转移方式是：
