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,每个数只能使用一次,确保在集合中的数字按顺序排列。