数字组合

数字组合

题目：

描述
给定一个候选数字的集合 candidates 和一个目标值 target。 找到 candidates 中所有的和为 target 的组合。

在同一个组合中, candidates 中的某个数字出现次数不限。

所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.
解集不能包含重复的组合.
样例
样例 1:

输入: candidates = [2, 3, 6, 7], target = 7
输出: [[7], [2, 2, 3]]
样例 2:

输入: candidates = [1], target = 3
输出: [[1, 1, 1]]

解题思路：防止出现重复答案，先将数组进行排序，组合的时候不选择重复元素即可

public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target: An integer
     * @return: A list of lists of integers
     */
    private List<List<Integer>> ans;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // write your code here
        ans = new ArrayList();
        Arrays.sort(candidates);
        dfs(candidates, 0, target, new ArrayList());
        return ans;
    }

    private void dfs(int[] candidates, int cur, int target, List<Integer> list) {
        if(target < 0) {
            return ;
        }
        
        if(target == 0) {
            ans.add(new ArrayList(list));
            return ;
        }
        
        for(int i = cur; i < candidates.length; i++) {
            if(i > 0 && candidates[i] == candidates[i - 1]) {
                continue ;
            }
            list.add(candidates[i]);
            dfs(candidates, i, target - candidates[i], list);
            list.remove(list.size() - 1);
        }
    }
}