Combination Sum

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]

有关组合求和的问题，我们采用回溯法，从一条路走下去，如果找到结果就记录下来，如果走到尽头没找到结果就开始回溯，因为题目要求每个数字可以使用多次，因此我们往下寻找答案的起始点都是从当前元素开始。其次，题目要求结果集为非降序列，所以我们要先将数组排序在做处理。代码如下：

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        List<List<Integer>> llist = new LinkedList<List<Integer>>();
        if(candidates == null || candidates.length == 0) return llist;
        java.util.Arrays.sort(candidates);
        getCombination(0, target, candidates, list, llist);
        return llist;
    }
    public void getCombination(int start, int target, int[] candidates, LinkedList<Integer> list, 
    List<List<Integer>> llist) {
        for(int i = start; i < candidates.length; i++) {
            if(target > candidates[i]) {
                list.add(candidates[i]);
                getCombination(i, target - candidates[i], candidates, list, llist);
                list.removeLast();
            } else if(target == candidates[i]) {
                list.add(candidates[i]);
                if(!llist.contains(list))
                    llist.add(new LinkedList<Integer>(list));
                list.removeLast();
            } else {
                return;
            }
        }
    }
}