【LeetCode】39. 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:

For example, given candidate set[2, 3, 6, 7] and target 7, A solution set is:

解题思路

回溯+剪枝 先对candidates升序排序，然后，遍历所有candidates，如果小于target，就可以加入当前的求解队列中。然后，更新target，递归向下查找。 那么，如何确保找到的解没有重复呢？ 首先，题目说明给出的candidates是没有重复的，这个不用考虑。 我们可以通过让求解队列升序排序来做剪枝。由于candidates本身有序，我们只需要每次递归时传入一个index，确保下一轮递归中从index出开始查找即可。 这样，就不会出现如下的重复情况

AC代码