Combination Sum

Combination Sum

---

大家新年快乐。

今天是一道有关数组和迭代的题目，来自LeetCode，难度为Medium，Acceptance为29.5%。

题目如下

---

Given a set of candidate numbers (C) 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.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
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] 

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

---

首次，该题还是有一定难度的，但是通过率并不低，思路也较为清晰。

然后，我们来分析该题。因为根据题意，每个数字可以选0次或者任意多次，所以这里很容易想到用递归；其次，因为这里要求所有的可能，为了避免重复，我们先对所有数排序。

然后递归，就要想递归的终止条件：

• 第一，当前值已经等于T了，此时可以终止，因为题目中给出了所有数都是正数。

• 第二，因为所有数都是正数，所以当前遍历到的数比T-current大的时候，可以终止。

最后，因为每个数可以选择多次，所以递归过程中不能每次遍历下一个数字，还是要从该数字开始，直到满足以上2个终止条件。

我们来看代码。

代码如下

---

Java版

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();
        Arrays.sort(candidates);
        dfs(ret, new LinkedList<Integer>(), 0, target, candidates);
        return ret;
    }
    
    public void dfs(List<List<Integer>> ret, LinkedList<Integer> list, int start, int gap,  int[] candidates) {
        if(gap == 0) {
            ret.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i = start; i < candidates.length && gap >= candidates[i]; i++) {
            list.add(candidates[i]);
            dfs(ret, list, i, gap - candidates[i], candidates);
            list.removeLast();
        }
    }
}