算法_回溯_组合总和

leetcode链接

1.解法

这道题和普通的组合问题的区别在于它可以重复取集合中的数值&＃xff0c;所以我们再代码实现的时候需要注意这一点。

因为组合问题就是回溯问题&＃xff0c;而回溯问题都可以画成树&＃xff0c;所以我们先画出图帮助分析&＃xff1a;

从图中我们看出一个规律&＃xff0c;就是当取得了一个元素后&＃xff0c;我们在下一次选择数值的时候&＃xff0c;集合就变为了该数值往后的数值集合&＃xff08;包括该数&＃xff09;。举个例子&＃xff0c;如果取了2&＃xff0c;那么下一次就要在[2,5,3]中选。如果取了5&＃xff0c;下一次就要在[5,3]中取。这为我们实现逻辑部分的代码提供了依据。

然后是回溯三部曲&＃xff1a;

1. 确定函数头和一些辅助变量&＃xff1a;

   result &＃61; [] # 存储最终稿答案path &＃61; [] # 存储当前取得的所有数值def backtracking(candidates,target,sum)


   因为参数是要在编写代码中确定的&＃xff0c;所以我这里先写上这三个参数&＃xff0c;后面看完代码大家就懂了。但这里还是简单说一下含义&＃xff0c;

   candidates代表的是当前取数的集合&＃xff0c;
   target代表的是目标数值&＃xff0c;
   sum代表的是已取得的数的总和。

2. 确定递归出口&＃xff1a;

   if sum > target:returnif sum &＃61;&＃61; target:result.append(path)return


   &＃xff08;1&＃xff09;当已取得的数值的和&＃xff0c;即sum&＃xff0c;比目标数值大的时候&＃xff0c;就直接退出该层递归&＃xff1b;

   &＃xff08;2&＃xff09;当已取得的数值的和&＃xff0c;即sum&＃xff0c;和目标数值一样大的时候&＃xff0c;就可以把取得的数值保存一下&＃xff0c;然后退出该层递归。

3. 确定递归逻辑&＃xff1a;

   for i in range(len(candidates)):path.append(candidates[i])sum &＃61; sum &＃43; candidates[i]backtracking(candidates[i:],target,sum)sum &＃61; sum - candidates[i]path.pop()


   每次递归都要从当前的集合中取数&＃xff0c;所以用for循环来完成取数操作&＃xff0c;然后每次都要把取得的数值存入path中&＃xff0c;sum加上对应的数值&＃xff0c;然后递归&＃xff0c;注意此时的candidates要变成该元素之后的所有元素组成的集合&＃xff08;包括该元素&＃xff09;&＃xff0c;然后回溯&＃xff0c;将sum减去加上的值&＃xff0c;path弹出对应的值。

总体代码为&＃xff1a;

def combinationSum(candidates, target):result &＃61; []path &＃61; []def backtracking(candidates,target,sum):if sum >target:returnif sum &＃61;&＃61; target:path1 &＃61; path.copy() # 如果不copy的话&＃xff0c;后面修改path的值&＃xff0c;result中的path也会改变result.append(path1)returnfor i in range(len(candidates)):path.append(candidates[i])sum &＃61; sum &＃43; candidates[i]backtracking(candidates[i:],target,sum)sum &＃61; sum - candidates[i]path.pop()backtracking(candidates,target,0)return result


2.优化

我们考虑如果我们将candidates从小到大排序后&＃xff0c;那么我们从最小的数值按照顺序开始取&＃xff0c;这样如果有一次取得的元素和刚好等于或者大于了target&＃xff0c;那么后面的该层循环后面的值都不用再取了&＃xff0c;因为一定会大于target。

所以我们可以在逻辑部分加一个判断&＃xff0c;如果当sum>target的时候&＃xff0c;那么就直接break就好了&＃xff0c;不过前提是要先将candidates从小到大排序。

所以修改后的代码为&＃xff1a;

def combinationSum(candidates, target):result &＃61; []path &＃61; []candidates &＃61; sorted(candidates)def backtracking(candidates,target,sum):if sum >target:returnif sum &＃61;&＃61; target:path1 &＃61; path.copy()result.append(path1)returnfor i in range(len(candidates)):path.append(candidates[i])sum &＃61; sum &＃43; candidates[i]if sum > target: # 剪枝sum &＃61; sum - candidates[i] # 注意判断完后也要回溯path.pop()breakbacktracking(candidates[i:],target,sum)sum &＃61; sum - candidates[i]path.pop()backtracking(candidates,target,0)return result


3.总结

剪枝不一定是在原有基础上剪枝&＃xff0c;有可能还需要先对集合或者其他要素进行一定操作之后才可以剪枝。