39.组合总和

这道题有点,,让我挺懵的,倒不是这道题本身的原因,而是golang的原因。。。

 

这道题是用回溯来解决的,假如不是无限制重复选取一个数相信会更简单一些,就直接回溯就行,每次添加一个数,target就减去这个数,直到target为0时,得到的数组结果就是一个集合,添加进结果中。如果小于0,直接返回。但是这道题是可以重复选择同一个数的,所以,回溯进去后不是从下一个数开始,而是还是当前的数,这里要注意的是一个回溯结束后,上一步的循环要把这个数从nums中移出去

代码如下:

39.组合总和

比较有意思的是最后的结果append到res中时必须是新生命一个slice,然后把nums的值给copy过来,我也不知道这是咋回事。。应该是golang的某个陷阱把。。不然就是错的。。有点懵逼。。

回溯的nums添加元素去除元素其实可以直接写成这样更方便,感觉也更好理解:

39.组合总和