Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

        又是求和问题,博主的使用递归的方法,虽然给出正确结果,但是存在效率的问题:

        代码比较长,下面总结一下递归法处理的思路:

1.先将数列进行排序,然后按照定和问题的思路来解决;

2.判断最小的数字是不是小于target_sum,如果小于target_sum,则这个数value入栈,右边的数字中需要和为target_sum – value,这样就编程了一个定和的递归问题。每次从中取出一个数,如果可以使和 小于 target,则继续取,如果 等于 target 则保存结果,如果大于target,则终止;

note:每次入栈,都对应一次出栈,递归法思路不好理,这一点一定要理解并且要作为基本常识。

3.由于遇到重复值需要跳过,则有下面这段经典代码:

        这段代码怎样理解呢,我们假设输入序列是[1 1 1 3 1 3 6],target是6,我们会担心得不到[1 1 1 3]这样的结果,事实上,这种担心是不必要的。第一次进栈的是1,后面的序列为[1 1 1 3 3 6],第二次进栈的是1,剩下的是[1 1 3 3 6] …… ,得到[1 1 1 3]后,事实上我们已经将第一个数字为1的情况都考察过了。当我们再次选取第一个数字时,如果我们不跳过,也就是说假设我们没有if这句代码,我们会得到三个 [1 1 1 3] 这种重复的答案,这其中还有玄机,遍历第一个数字时的重复会增加一个,遍历第二个数字带来的重复也会增加一个,遍历第三个数字时的重复也会增加一个,最先发生的是最后一种情况,那么我们就能够理解代码中的这两处的if跳过了。

        OK,See You Next Chapter!

发表评论

电子邮件地址不会被公开。 必填项已用*标注