39. 组合总和

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

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 = removeDuplicates2(candidates);

        dfs(nums, 0, new ArrayList<Integer>(), target, 0, results);

        return results;
    }

    /**
     * 排序去重复
     *
     * @param candidates
     * @return
     */
    private int[] removeDuplicates2(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;
    }

    /**
     * 深度优先搜索
     *
     * @param nums        数组
     * @param startIndex  开始索引
     * @param combination 和的组合list
     * @param target      目标值
     * @param sum         和
     * @param results     结果
     */
    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);
        }
    }