題目

給出一組候選數(shù)字(C)和目標(biāo)數(shù)字(T),找到C中所有的組合唐础，使找出的數(shù)字和為T晦款。C中的數(shù)字可以無限制重復(fù)被選取规个。

例如,給出候選數(shù)組[2,3,6,7]和目標(biāo)數(shù)字7凤薛，所求的解為：

[7]，

[2,2,3]

注意事項

所有的數(shù)字(包括目標(biāo)數(shù)字)均為正整數(shù)诞仓。
元素組合(a1, a2, … , ak)必須是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)缤苫。
解集不能包含重復(fù)的組合。

樣例
給出候選數(shù)組[2,3,6,7]和目標(biāo)數(shù)字7

返回 [[7],[2,2,3]]

分析

也是典型的深度搜索回溯問題墅拭，不過需要注意一些點活玲，首先我們需要將數(shù)組排序，然后移除掉重復(fù)元素谍婉，然后由于一個元素可以重復(fù)出現(xiàn)舒憾，所以start應(yīng)該是上一次的值。

代碼

public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return results;
        }
        
        int[] nums = removeDuplicates(candidates);
        
        dfs(nums, 0, new ArrayList<Integer>(), target,0, results);
        
        return results;
    }
    
    private int[] removeDuplicates(int[] candidates) {
        Arrays.sort(candidates);
        
        int index = 0;
        for (int i = 0; i < candidates.length; i++) {
            if (candidates[i] != candidates[index]) {
                candidates[++index] = candidates[i];
            }
        }
        
        int[] nums = new int[index + 1];
        for (int i = 0; i < index + 1; i++) {
            nums[i] = candidates[i];
        }
        
        return nums;
    }
    
    private void dfs(int[] nums,
                     int startIndex,
                     List<Integer> combination,
                     int target,
                     int sum,
                     List<List<Integer>> results) {
        if (sum == target) {
            results.add(new ArrayList<Integer>(combination));
            return;
        }
        
        for (int i = startIndex; i < nums.length; i++) {
            if (target < nums[i] + sum) {
                break;
            }
            combination.add(nums[i]);
            dfs(nums, i, combination, target,sum + nums[i], results);
            combination.remove(combination.size() - 1);
        }
    }
}