leetcode之Combination Sum 问题

问题描述：

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations inC where the candidate numbers sums toT.

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]
]

问题来源：Combination Sum (具体地址：https://leetcode.com/problems/combination-sum/#/description)

思路：相信这道题的意思很好理解，实在不理解看看示例肯定就知道了，在这我就不翻译了。反倒是几个小细节值得我们关注，刚开始给的数组当中是没有重复数字的，但是你选出的每一个小的集合当中都是可以包含重复数字的，但是每个小集合是不允许重复的。是不是有点晕了？我的意思就是上面的2， 3， 6， 7没有重复数字吧，但是你选出的每个小集合[2, 2, 3]里面的数字是允许重复的，但是呢，有[2, 2, 3]之后，就不能包括[2, 3, 2]或[3, 2, 2]等其他的组合了。这是题目的意图，我们就先说到这。

至于这道题的套路，有套路？没错，这种题确实是有套路的，都可以总结为回溯问题(Backtracking)，这上面介绍了经典的八皇后问题就是回溯问题，图的遍历(DFS)其实也是采用的回溯，当然还有很多backtracing的运用场景。个人简单直白的理解就是：试着往前走一走，瞧一瞧，实在不行咱就退回来(回溯的意思就是在这)。当然，这是个人的大白话，专业术语绝对不可能是这样的，专业的解释上面已经给了相应的链接了。至于套路，往下看看下面的backtrace方法你就能明白理解了。后面的Combination Sum II(Combination Sum II) 和Combination Sum III(Combination Sum III)都是这个套路，只是有很少的一部分相应地调整了一下。

代码：

注意：这里小集合里是允许元素重复的，但是在这对数组排序其实是没多大作用的，跑出来的结果也是一样的，但是作为做这种题的套路，一般都会需要对数组进行排序，在后面的Combination Sum II和Combination Sum III的解析会解释一下的。

下面就是主体部分(也就是上文说的套路部分)：

体会：发现刷leetcode需要多总结整理啊，好多都是同一个思路套路，看来写写博客做做记录也还是不错的学习方式啊。