Leetcode216&39

1、Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]] 这种题的思路无非就是从头开始，一个个的找，个数和总和都不满足时就添加，从小到大，如果个数和总和有一个“超”了，就删除这个，加入下一个，只有当个数和总和都满足时，才存入。在“超”之前，我们需要递增的就只有需要加入的数字，隐形递增的还有temp的size()。当个数超了或者总和超了（推一下可以发现，如果每次都是从小到大加入元素，如果总和超了，那一定是伴随着个数超了）return，接下来需要删除刚刚添加的元素，然后返回上一层。。。。 由于n和k都是不固定，简单的几层循环是肯定搞不定了，这种情况一般就要用递归。

2、Combination Sum Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ] 这个题如果按照上题思路，就是先排个序，就依然是从小到大一个个加，区别是每组内元素可重复，所以当不“超”时，元素序号不需要递增，一直加下去直到“超”了。