leetCode 典型回溯例子

39题,翻译题目:给定一组候选集和一个目标值,在c的所有组合中,找出所有总和等于T的组合。

候选数组c中同一个数可以被选择多次(不限次数)

分析:

典型的回溯法应用

对数组里面的每个数,用递归的方式相加,每次递归将和sum与target作比较,若相等则加入结果vector,sum>target则舍弃,

并返回false,若sum<target,则继续进行递归,若sum>target,则回溯到上一层,重新以数组中的下一个数开始递归。

第一种sum=target的情况下,在加入结果vector后回溯(此时不应再累加),要将当前一种结果最后加入的元素pop_back(),并继续对后面的元素进行递归;

第二种:sum>target的情况下,则需要将当前的结果的最后加入的元素pop-back(),并继续对后面的元素进行递归。

第三种:sum<target的情况下,直接以当前数继续递归。

注意sum<target的情况下,元素可以重复,所以下一次递归总是从当前递归元素开始。

40题,翻译题目:

给定一组候选集(c)和一个目标值T,在c的所有组合中,找出所有总和等于T的组合。

候选数组c中每一个数字只能使用一次。

分析:

典型的回溯法应用。

这道题跟上一道题基本一模一样,唯一区别就是每个数只能用一次,因此代码上只需要改一点点就行,即下一层递归

不能再从当前数开始,而要从下一个数开始了。

41题:翻译题目

找到有K个数组成的所有可能组合,加起来等于数n

k个数取值1到9,每个数只能使用一次,确保在集合中的数字按顺序排列。

原文地址:https://www.cnblogs.com/heruonan/p/8337990.html