backtracking——39. 组合总和

组合求和,这个题是没有顺序的,就是[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

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。