组合求和,这个题是没有顺序的,就是[2,3]和[3,2]是同一个结果。
看了一个帖子里面的总结:
1 排列问题,讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时),需要记录哪些数字已经使用过,此时用 used 数组;
2 组合问题,不讲究顺序(即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时),需要按照某种顺序搜索,此时使用 begin 变量。
所以我们这里用一个begin 变量,还有一个要注意的是,因为可以重复使用,所以可以递归的时候begin也不要加1。
而且还要加一个判断——if(candidates[i] <= target)去剪枝。
code:
https://github.com/hanleirx/LeetCode/blob/master/39.%20%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C