雅虎搜狐创新工场微软算法题(doc 8页)

雅虎搜狐创新工场微软算法题内容提要：
首先说一下这个题的解题思想。
1.选取某一个开始长度，开始组合小木棒，这个开始长度的限制条件为 不小于木棒最大长度，不大于所有木棒长度和，能被长度和整除
2.从可用的最长的那根小木棒开始组合木棒，找出所有的结果集，找到结果集后开始组合下一根木棒。
3.直到所有的小木棒都被组合完成，搜索结束。
思路：
1.len>=max{a[i]} && len|sum(a[i])
2.为了避免重复搜索，令每个大S的组成中，小S的长度依次递减，这样就需要在搜索之前对a[i]排序；全部的大S的第一段小S依次递减
3.如果在某层搜索中，尝试将a[j]加入到第i个大S的组成中，如果最终a[j]没有被使用，且a[j+1]==a[j]，不需要继续尝试a[j+1]
4.如果此次是在尝试第i个大S的第一段小S a[j]，a[j]为当前可以被使用的最长的小S，如果此次尝试失败，直接退出搜索，即退回到对第i-1个大S的搜索。试想：失败说明现在使用a[j]是不可行的，那么什么时候使用a[j]呢？如果没有退出搜索，肯定会在之后的搜索中使用a[j]，因为所有的小S必须都使用。之后的a[j]和最初尝试的a[j]有什么不同呢？没有不同，它们等价，因此之后也不会成功，不需要继续搜索。

..............................