Combination Sum(Medium)组合数之和

Leetcode Source

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.

Notes:

1. All numbers (including target) will be positive integers.
2. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
3. 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]

解题思路：回溯+DFS

因为我们可以任意组合任意多个数，看其和是否是目标数，而且还要返回所有可能的组合，所以我们必须遍历所有可能性才能求解。为了避免重复遍历，我们搜索的时候只搜索当前或之后的数，而不再搜索前面的数。因为我们先将较小的数计算完，所以到较大的数时我们就不用再考虑有较小的数的情况了。这题是非常基本且典型的深度优先搜索并返回路径的题。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new LinkedList<List<Integer>>();

    if(candidates == null || candidates.length == 0)
        return result;

    List<Integer> current = new LinkedList<Integer>();;
    Arrays.sort(candidates);

    combinationSum(candidates, target, 0, current, result);

    return result;
}

public void combinationSum(int[] candidates, int target, int start, List<Integer> curr, List<List<Integer>> result){
    if(target == 0){
        List<Integer> temp = new LinkedList<Integer>(curr);
        result.add(temp);
        return;
    }

    for(int i=start; i<candidates.length; i++){
        if(target < candidates[i])
            return;

        curr.add(candidates[i]);
        combinationSum(candidates, target - candidates[i], i, curr, result);
        curr.remove(curr.size()-1);
    }
}

References:

1 Coin Changes