递归函数:自己调用自己的函数。
利用递归方法,将大问题拆成若干个小问题,再整合成大问题的方法称为分治法。
基本步骤:
1.将问题“分割”成局部问题。(Divide)
2.递归求解局部问题。(Solve)
3.整合局部问题,解决原问题。(Conquer)
简单的例子:将n个元素要么用0,要么用1来表示,并将其全部罗列。
练习:现有长度为n的数列A和m个整数,判断A中任意几个元素相加是否能得到m。
A中每个元素只能使用一次。
输入 输出
5 no
1 5 7 10 21 no
4 yes
2 4 17 8 yes